Pagini recente » Cod sursa (job #1889631) | Cod sursa (job #2854580) | Cod sursa (job #1775431) | Cod sursa (job #591276) | Cod sursa (job #1404071)
#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]=++a;
++j;
}
else if(a>0)
{
a=prefix[a-1];
}
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;
}
if(j>=l2)
{
j=prefix[j-1];
if(nr<1000)
rez[nr++]=i-l2;
}
}
}
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;
}