Pagini recente » Profil M@2Te4i | Istoria paginii template/borderou | Istoria paginii utilizator/anca-sorana | Monitorul de evaluare | Cod sursa (job #2469714)
#include <fstream>
#include <string.h>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int rez, v[1000], k;
void computeLPSArray(char* pat, int M, int* lps);
void KMPSearch(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[2000];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
++rez;
if (k <= 1000) {
v[k] = i - j;
++k;
}
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(char* pat, int M, int* lps)
{
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0) {
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int main() {
char pat[2000], txt[2000];
cin >> pat;
cin >> txt;
KMPSearch(pat, txt);
cout << rez << "\n";
for (int i = 0; v[i] != 0 && i < 1000; ++i)
cout << v[i] << " ";
return 0;
}