Pagini recente » Cod sursa (job #333363) | Cod sursa (job #2575481) | Cod sursa (job #697533) | Cod sursa (job #1768967) | Cod sursa (job #3209875)
#include <bits/stdc++.h>
#define MAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sirA[MAX],sirB[MAX];
int lpsA[MAX],raspB[MAX];
int ind[1005];
int main()
{
fin.getline(sirA,MAX);
fin.getline(sirB,MAX);
int i;
for(i=1;sirA[i];++i)
{
int lg=lpsA[i-1];
while(lg && sirA[lg]!=sirA[i])
lg=lpsA[lg-1];
if(sirA[lg]==sirA[i])
lpsA[i]=lg+1;
}
int n=0;
int sz=strlen(sirA);
for(i=0;sirB[i];++i)
{
int lg=raspB[i-1];
while(lg && sirA[lg]!=sirB[i])
lg=lpsA[lg-1];
if(sirA[lg]==sirB[i])
raspB[i]=lg+1;
if(raspB[i]==sz)
{
++n;
if(n<=1000)
ind[n]=i-sz+1;
}
}
fout<<n<<'\n';
for(i=1;i<=min(n,1000);++i)
fout<<ind[i]<<' ';
return 0;
}