Pagini recente » Cod sursa (job #1537069) | Cod sursa (job #1630328) | Cod sursa (job #3202094) | Cod sursa (job #2351258) | Cod sursa (job #1133972)
#include<cstring>
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000001],s2[2000001];
int sar[2000001],n1,n2,nr,sol[1001];
void completeaza()
{
for(int i=2;i<=n1;i++)
if(s1[i-1]==s1[sar[i-1]])
sar[i]=sar[i-1]+1;
}
void kmp()
{
int i,j,k=0,nrap=0;
for(i=0;i<n2;)
{
j=0;k=i;
while(s2[k]==s1[j]&&j<n1&&k<n2){k++;j++;}
if(j==n1){nr++;if(nr<=1000)sol[++nrap]=i;}
i=k-sar[j];
}
g<<nr<<'\n';
for(i=1;i<=nrap;i++)
g<<sol[i]<<" ";
}
int main()
{
sar[0]=-1;sar[1]=0;
f.getline(s1,2000001);
f.getline(s2,2000001);
n1=strlen(s1);
n2=strlen(s2);
completeaza();
kmp();
/*for(i=0;i<n1;i++)
g<<sar[i]<<" ";*/
return 0;
}