Pagini recente » Cod sursa (job #676540) | Monitorul de evaluare | Monitorul de evaluare | Statistici Nituica Andrei-Sebastian (zugafa) | Cod sursa (job #546147)
Cod sursa(job #546147)
#include <fstream>
using namespace std;
char p[2000002],s[2000002];
int v[2000002],k,q,m,i,n,a[1005],sol;
void prefix(char p[])
{
v[1]=0;
k=0;
for(q=2;q<=m;q++)
{
while(k>0 && p[k+1]!=p[q])
k=v[k];
if(p[k+1]==p[q])
{ k++;
v[q]=k;
}
}
}
void KMP(char p[],char s[])
{
prefix(p);
q=0;
for(i=1;i<=n;i++)
{
while(q>0&&p[q+1]!=s[i])
q=v[q];
if(p[q+1]==s[i])
{ q++;
if(q==m)
{ sol++;
if (sol<1001)
a[sol]=i-q;
} }
}
}
int main()
{ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p+1,2000002);
f.getline(s+1,2000002);
p[0]=' ';s[0]=' ';
m=strlen(p)-1;
n=strlen(s)-1;
KMP(p,s);
g<<sol<<"\n";
for(i=1;i<=sol;i++)
g<<a[i]<<" ";
return 0;
}