Pagini recente » Cod sursa (job #1365571) | Rating Stanciu Anastasia-Steliana (Anastasia12) | Cod sursa (job #2355421) | Cod sursa (job #1706263) | Cod sursa (job #2803285)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000005
char a[NMAX], b[NMAX];
int n, m, urmator[NMAX];
void init_urm(char *p)
{
int i, j;
urmator[0] = -1;
for (i=0, j=-1;i<m;i++,j++,urmator[i]=j){
while(j>=0 && p[i] != p[j]){
j = urmator[j];
}
}
}
int ans[1005];
void kmp(char *a, char *p)
{
int i, j, nr = 0;
for (i=0,j=0;j<m && i<n;i++, j++){
while(j >= 0 && a[i] != p[j]){
j = urmator[j];
}
/*if (p[j] == a[i])
j ++;*/
if (j == m - 1){
//fout << j << ' ';
j = urmator[j];
nr ++;
if (nr <= 1000){
ans[nr] = i - m;
}
}
}
fout << nr << '\n';
nr = min(nr, 1000);
for (int i=1;i<=nr;i++){
fout << ans[i] << ' ';
}
}
int main() {
fin.getline(b, NMAX);
fin.getline(a, NMAX);
n = strlen(a);
m = strlen(b);
init_urm(b);
kmp(a, b);
return 0;
}