Pagini recente » Cod sursa (job #3175573) | Borderou de evaluare (job #815511) | Cod sursa (job #1090297) | Cod sursa (job #2060134) | Cod sursa (job #1724787)
#include <fstream>
#include <cstring>
#define N 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[N],B[N];
int n,m,pi[N],i,q,nr,poz[1010];
void pref(){
int i,q=0;
pi[0]=0;
for(i=2;i<=m;i++)
{
while(q && A[q]!=A[i-1])
q=pi[q];
if(A[q]==A[i-1])
q++;
pi[i]=q;
}
}
int main(){
fin.get(A,N); fin.get();
fin.get(B,N); fin.get();
m=strlen(A);
n=strlen(B);
pref();
for(i=1;i<=n;i++)
{
while(q && A[q]!=B[i-1])
q=pi[q];
if(A[q]==B[i-1])
q++;
if(q==m)
{
q=pi[m];
nr++;
if(nr<=1000)
poz[nr]=i-m;
}
}
fout<<nr<<'\n';
for(i=1;i<=nr && i<=1000;i++)
fout<<poz[i]<<" ";
fin.close();
fout.close();
return 0;
}