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