Pagini recente » Cod sursa (job #2574603) | Cod sursa (job #2563085) | Cod sursa (job #3210037) | Cod sursa (job #2758306) | Cod sursa (job #1045630)
#include<fstream>
#define numaru 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int q[numaru],la,lb,r,rr[numaru];
char a[numaru],b[numaru];
void F2(char s[],int &l)
{
l=strlen(s);
int i;
for(i=l;i>0;s[i]=s[i-1],--i);
s[0]='#';
s[l+1]='\0';
}
void F()
{
int k=0,i;
q[1]=0;
for(i=2;i<=la;++i)
{
while(k>0 && a[k+1]!=a[i])k=q[k];
if(a[k+1]==a[i])++k;
q[i]=k;
}
}
void strmatch()
{
int k=0,i;
for(i=1;i<=lb;++i)
{
while(k>0 && a[k+1]!=b[i])k=q[k];
if(a[k+1]==b[i])++k;
if(k==la){ rr[r++]=i-la; k=q[k]; }
}
}
int main()
{
int i;
f>>a>>b;
F2(a,la);F2(b,lb);
F();
strmatch();
r=(r<1000)?r:1000;
g<<r<<"\n";
for(i=0;i<r;++i) g<<rr[i]<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}