Pagini recente » Cod sursa (job #1396739) | Cod sursa (job #2596588) | Cod sursa (job #1272233) | Cod sursa (job #1664201) | Cod sursa (job #2875765)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
int sol[2000002],lps[2000002],k;
int main()
{int n,m,x;
f>>a>>b;
n=strlen(a);
m=strlen(b);
for (int i=1;i<n;i++) {x=lps[i-1];
while (x>0 && a[x]!=a[i]) x=lps[x];
if (a[x]==a[i]) x++;
lps[i]=x;
}
x=0;
for (int i=0;i<m;i++) {while (x>0 && a[x]!=b[i]) x=lps[x];
if (a[x]==b[i]) x++;
if (x==n) k++,sol[k]=i-n+1;
}
g<<k<<'\n';
for (int i=1;i<=k;i++) g<<sol[i]<<' ';
}