Pagini recente » Cod sursa (job #1556101) | Cod sursa (job #1575299) | Cod sursa (job #1208367) | Cod sursa (job #1430630) | Cod sursa (job #1726431)
///KMP
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int pi[NMAX];
char p[NMAX],
t[NMAX];
int main(void) {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
vector<int> ans;
int n, m, q;
scanf("%s%s",p+1,t+1);
n = strlen(t+1);
m = strlen(p+1);
if(n < m) {
printf("%d\n",0);
fclose(stdin);
fclose(stdout);
}
pi[1] = 0;
for(int i=2, k=0; i<=m; ++i) {
while(k>0 && p[k+1]!=p[i])
k = pi[k];
if(p[k+1]==p[i])
++k;
pi[i] = k;
}
q = 0;
for(int i=1; i<=n; ++i) {
while(q>0 && p[q+1]!=t[i])
q = pi[q];
if(p[q+1]==t[i])
++q;
if(q==m)
ans.push_back(i-m);
}
printf("%d\n",ans.size());
for(auto i:ans)
printf("%d ",i);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}