Pagini recente » Cod sursa (job #391237) | Cod sursa (job #1140877) | Cod sursa (job #1202552) | Cod sursa (job #1449741) | Cod sursa (job #1403070)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
char s1[2000000],s2[2000000];
int prefix[2000000];
int rez[1000];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int nr=0;
void pref(int prefix[],char s2[])
{
int a=0;
int j=1;
prefix[0]=a;
int l=strlen(s2);
while(j<l)
{
if(s2[j]==s2[a])
{
prefix[j]=prefix[j-1] +1;
++a;
++j;
}
else if(a>0)
{
a=prefix[j];
}
else ++j;
}
}
void KMP(char s1[],char s2[])
{
pref(prefix,s2);
int i=0,j=0,l1=strlen(s1),l2=strlen(s2);
while(i<l1)
{
if(j<l2)
{
if(s1[i]==s2[j])
{
++j;
++i;
}
else if(j>0)
{
j=prefix[j-1];
}
else
++i;
}
else
{
j=0;
rez[nr++]=i-l2;
--i;
}
}
}
int main()
{
in>>s2;
in>>s1;
KMP(s1,s2);
out<<nr<<endl;
for(int i=0;i<nr && i<1000;i++)
out<<rez[i]<<" ";
in.close();
out.close();
return 0;
}