Pagini recente » Cod sursa (job #2811985) | Cod sursa (job #1055625) | Cod sursa (job #1166075) | Cod sursa (job #3224354) | Cod sursa (job #671076)
Cod sursa(job #671076)
#include<fstream>
#include<string>
using namespace std;
char T[2000001], P[2000001];
long p, t, k, L[200000], D[2000001], m, n, i;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
fin.getline(P, 2000001);
fin.getline(T, 2000001);
m=strlen(P);
n=strlen(T);
L[0]=0;
k=-1;
for(p=1;p<m;p++)
{
while(P[k+1]!=P[p] && k>0)
k=L[k];
if(P[k+1]==P[p])
k++;
L[p]=k;
}
k=-1;
for(t=0;t<n;t++)
{
while(k>0 && T[t]!=P[k+1])
k=L[k];
if(T[t]==P[k+1])
k++;
if(k==m-1)
{
D[++i]=t-m;
k=L[k];
}
}
fout<<i<<'\n';
for(p=1;p<=i;p++)
fout<<D[p]+1<<' ';
fout<<'\n';
fin.close();
fout.close();
return 0;
}