Pagini recente » Cod sursa (job #138658) | Cod sursa (job #2258947) | Cod sursa (job #1843412) | Cod sursa (job #891539) | Cod sursa (job #446920)
Cod sursa(job #446920)
#include<fstream>
using namespace std;
#define nmax 2000001
char A[nmax],B[nmax];
int L[nmax],poz[1001],pozz,a,b;
void prefix()
{
int k,p;
L[1]=0;
for(p=2;p<=a;p++)
{
k=L[p-1];
while(k>0 && A[k+1]!=A[p]) k=L[k];
if(A[k+1]==A[p]) k++;
L[p]=k;
}
}
void KMP()
{
int k=0,t;
for(t=1;t<=b;t++)
{
while(k>0 && A[k+1]!=B[t]) k=L[k];
if(A[k+1]==B[t]) k++;
if(k==a)
{
pozz++;
if(pozz<1001) poz[pozz]=t-a;
k=L[k];
}
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(A+1,nmax,'\n');a=strlen(A+1);
f.getline(B+1,nmax,'\n');b=strlen(B+1);
prefix();KMP();g<<pozz<<'\n';
if(pozz>1000) pozz=1000;
for(int i=1;i<=pozz;i++) g<<poz[i]<<" ";
}