Pagini recente » Cod sursa (job #976415) | Cod sursa (job #312847) | Cod sursa (job #2816301) | Cod sursa (job #1063284) | Cod sursa (job #2073950)
#include <bits/stdc++.h>
const int NMAX = 2000005;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX], s[NMAX];
int n, m, pi[NMAX], poz[NMAX], k;
void prefix() {
int i, j=0;
pi[1]=0;
for(i=2; i<=n; i++) {
while(j && a[i]!=a[j+1])
j=pi[j];
if(a[i]==a[j+1])
j++;
pi[i]=j;
}
}
void kmp() {
int i, j=0;
for(i=1; i<=m; i++) {
while(j && s[i]!=a[j+1])
j=pi[j];
if(s[i]==a[j+1])
j++;
if(j==n) {
k++;
if(k<=1000)
poz[k]=i-n;
j=pi[j];
}
}
}
int main() {
fin>>(a+1);
n=strlen(a+1);
fin>>(s+1);
m=strlen(s+1);
prefix();
kmp();
fout<<k<<'\n';
int minim=min(1000, k);
for(int i=1; i<=minim; i++)
fout<<poz[i]<<' ';
return 0;
}