Pagini recente » Cod sursa (job #2837326) | Cod sursa (job #2631541) | Cod sursa (job #301473) | Cod sursa (job #2093433) | Cod sursa (job #1167370)
#include<fstream>
#include<string>
using namespace std;
int nrOfMatches = 0, matches[1005],kmpNext[2000000];
ifstream inputStream("strmatch.in");
ofstream outputStream("strmatch.out");
void preKmp(char *x, int m, int kmpNext[]) {
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
void KMP(char *x, int m, char *y, int n) {
int i, j;
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
matches[nrOfMatches] = j - i;
nrOfMatches++;
i = kmpNext[i];
}
}
}
int main()
{
string pattern, subject;
getline(inputStream, pattern);
getline(inputStream, subject);
char* patt = const_cast<char*>(pattern.c_str());
char* subj = const_cast<char*>(subject.c_str());
KMP(patt, pattern.size(), subj, subject.size());
outputStream << nrOfMatches << std::endl;
for (int i = 0; i < nrOfMatches; i++)
outputStream << matches[i] << " ";
return 0;
}