我正在尝试使用模式匹配算法实现抄袭检测软件。我在这里遇到了KMP 算法并尝试了 c# 实现。我可以看到实际文档的速度并不快（不是字符串，我使用 iText 上传了两个 pdf 文档，并在这两篇论文中得到了检查抄袭的实现。大约 50 页）。
这真的很慢，我不知道该怎么做。我也看过Boyer Moore和Rabin Karp。
我目前正在做的是获取文档中的每个句子（拆分为“。”）并扫描整个参考文档（第二个文档）以进行匹配。然后接下一句话，依此类推……我完全知道这可能非常昂贵。但我不知道如何在不使用这种方法的情况下实现字符串（模式）匹配。这是我最后一年的项目，我得到了一个主题，所以我必须使用字符串匹配。（不允许做基于引用的抄袭、语义或向量空间。）
文本和模式越大，算法越慢（非常慢，甚至不是相当慢）。还有另一种我不知道的方法吗？还是有更快的算法供我使用这种我的方法？
编辑
我的代码如下：`
public class MatchChecker
{
public void KMPSearch(string pattern, string text, int page)
{
if (pattern.Trim() != "")
{
int M = pattern.Length;
int N = text.Length;
// create lps[] that will hold the longest
// prefix suffix values for pattern
int[] lps = new int[M];
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[]
// array)
computeLPSArray(pattern, M, lps);
int i = 0; //index for text[]
while (i < N)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == M)
{
Console.WriteLine("Found pattern " + pattern + " at page " + page);
j = lps[j - 1];
}
//mismatch after j matches
else if (i < N && pattern[j] != text[i])
{
//Do not match lps[0..lps[j-1]] characters,
//they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
}
private void computeLPSArray(string pattern, int M, int[] lps)
{
//length of the previous longest prefix suffix
int length = 0;
int i = 1;
lps[0] = 0; //lps[0]is always 0
//the loop calculates lps[i] for i = 1 to M - 1
while (i < M)
{
if (pattern[i] == pattern[length])
{
length++;
lps[i] = length;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (length != 0)
{
length = lps[length - 1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = length;
i++;
}
}
}
}
public string ReadDocPDF()
{
List<string> pages = new List<string>();
PdfReader reader2 = new PdfReader(@"C:\Users\obn\Desktop\project\chapter1.pdf");
string strText = string.Empty;
for (int page = 1; page <= reader2.NumberOfPages; page++)
{
ITextExtractionStrategy its = new SimpleTextExtractionStrategy();
PdfReader reader = new PdfReader(@"C:\Users\obn\Desktop\project\chapter1.pdf");
String s = PdfTextExtractor.GetTextFromPage(reader, page, its);
s = Regex.Replace(Encoding.UTF8.GetString(ASCIIEncoding.Convert(Encoding.Default, Encoding.UTF8, Encoding.Default.GetBytes(s))).Replace(",", ""), "[0-9]", "").ToLower();
pages.Add(s);
strText = strText + s;
reader.Close();
}
return strText;
}
public void CheckForPlag()
{
string document = ReadDocPDF().Trim();
string[] sentences = document.Split(new string[] { "\n", "\t\n\r", ". ", "." }, StringSplitOptions.RemoveEmptyEntries);
foreach(string sentence in sentences) {
PdfReader reader2 = new PdfReader(@"C:\Users\obn\Documents\visual studio 2015\Projects\PlagDetector\PlagDetector\bin\Debug\test3.pdf");
for (int page = 1; page <= reader2.NumberOfPages; page++)
{
ITextExtractionStrategy its = new SimpleTextExtractionStrategy();
PdfReader reader = new PdfReader(@"C:\Users\obn\Documents\visual studio 2015\Projects\PlagDetector\PlagDetector\bin\Debug\test3.pdf");
String s = PdfTextExtractor.GetTextFromPage(reader, page, its);
s = Regex.Replace(Encoding.UTF8.GetString(ASCIIEncoding.Convert(Encoding.Default, Encoding.UTF8, Encoding.Default.GetBytes(s))).Trim().Replace(".","").Replace(",","").Replace("\n", ""), "[0-9]", "").ToLower();
KMPSearch(sentence, s, page);
reader.Close();
}
}
}
}`