Pagini recente » Cod sursa (job #3041236) | Cod sursa (job #2836799) | Istoria paginii descriere/ordonare/reducere | Cod sursa (job #1660712) | Cod sursa (job #2193707)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int lmax = 1000;
const int nmax = 2000000;
int n, m;
int matches;
int sol[1 + lmax];
int lps[1 + nmax];
char txt[1 + nmax], pat[1 + nmax];
int main() {
cin >> (pat + 1);
cin >> (txt + 1);
n = strlen(txt + 1);
m = strlen(pat + 1);
// calculez lps-ul
int i = 0, j = 2;
lps[1] = 0;
while(j <= n) {
if(pat[i + 1] == pat[j]) {
i++;
lps[j] = i;
j++;
} else {
if(i)
i = lps[i];
else {
lps[j] = 0;
j++;
}
}
}
// fac match-urile
i = 1;
j = 0;
while(i <= n) {
if(txt[i] == pat[j + 1]) {
i++;
j++;
}
if(j == m) {
matches++;
if(lmax >= matches)
sol[matches] = i - j - 1;
j = lps[j];
} else if(i <= n && txt[i] != pat[j + 1]) {
if(j)
j = lps[j];
else
i++;
}
}
cout << matches << "\n";
matches = min(matches, lmax);
for(int i = 1; i <= matches; i++)
cout << sol[i] << " ";
return 0;
}