Несложный вопрос по алгоритму
Цитата:
#include <iostream>
using namespace std;
int main()
{
char T[40000],S[10000];
int j,n,m,v=0,w=0,k=1,P = 9941,D=256;
/*
Ввод текста и образца
*/
for(int i=1;i<=m;i++)
{
v=(v*D+(int)S[i])%P;
w=(w*D+(int)T[i])%P;
}
for(int i=1;i<=m-1;i++)
k=(k*D)%P;//k имеет значение остатка деления Dm-1 на P<br />
for(int i=m+1;i<=n+1;i++)
{
if(w==v){j=0;//если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они
while((j<m)&(S[j+1]==T[i-m+j])){j++;}
if(j==m) cout << "Образец входит в текст начиная с" <<i-m<<"-го символа";//окончательная проверка
}
if(i<=n) w=(D*(w+P-(((int)T[i-m])*k)%P))+(((int)T[i])%P);
}
return 0;
}
|
Это Алгоритм Рабина-Карпа. Вопрос как дополнить программу, чтобы можно было вводить текст и искомую строку, сейчас в программе этого не реализованно. |
