Pagini recente » Cod sursa (job #1958031) | Istoria paginii utilizator/bielovechocolate | Cod sursa (job #2553638) | Cod sursa (job #2488464) | Cod sursa (job #2322359)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[2000005],B[2000005];
int pi[2000005];
int main()
{
int lc=0,poz[1005],nr=0,i,n,m;
//in.getline(A,2000005);
//in.getline(B,2000005);
in>>A;//in >> (A + 1);
in>>B;
pi[0]=lc;
for(i=strlen(A)+1; i>=1; i--)
A[i]=A[i-1];
for(i=strlen(B)+1; i>=1; i--)
B[i]=B[i-1];
n=strlen(A);
m=strlen(B);
for(i=2; i<n; i++)
{
while(lc>0 && A[i]!=A[lc+1])
{
lc=pi[lc];
}
if(A[i]==A[lc+1])
lc++;
pi[i]=lc;
}
lc=0;
for(i=1; i<m; i++)
{
while(lc>0 && B[i]!=A[lc+1])
{
lc=pi[lc];
}
if(B[i]==A[lc+1])
lc++;
if(lc==strlen(A)-1)
{
nr++;
if(nr<=1000)
poz[nr]=i-n+1;
}
}
out<<nr<<'\n';
for(i=1; i<=nr; i++)
out<<poz[i]<<" ";
return 0;
}