Pagini recente » Cod sursa (job #224620) | Cod sursa (job #702213) | Cod sursa (job #2512942) | Cod sursa (job #3151594) | Cod sursa (job #552349)
Cod sursa(job #552349)
#include<iostream.h>
#include<fstream.h>
#include<string.h>
void prefix(char *N,int *pi)
{ int n,k,i;
n=strlen(N);
k=0;
pi[0]=0;
for(i=1;i<n;i++)
{
while(k>0&& N[k]!=N[i])
k=pi[k-1];
if(N[k]==N[i])
k++;
pi[i]=k;
}
}
int main()
{
char *N = new char[2000001];
char *M = new char[2000001];
int i,n,m,q,a[1000],t,s;
int *pi = new int[2000000];
ifstream f("strmatch.in");
f>>N>>M;
f.close();
prefix(N,pi);
t=s=0;
m=strlen(M);
n=strlen(N);
q=0;
ofstream g("strmatch.out");
for(i=0;i<m;i++)
{
while(q>0 && N[q]!=M[i])
q=pi[q-1];
if(N[q]==M[i])
q++;
if(q==n&&t<1000) {a[t]=i-n+1; t++; s++;}
if(q==n&&t>999) s++;
}
if(s>999) s--;
g<<s<<'\n';
for(i=0;i<t;i++)
g<<a[i]<<" ";
return 0;
}