Pagini recente » Cod sursa (job #1366849) | Cod sursa (job #1222444) | Cod sursa (job #450132) | Cod sursa (job #943041) | Cod sursa (job #2330766)
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
FILE *f,*g;
char a[2000002],b[2000002];
int aa,bb,pi[2000002],ss;
deque <int> q;
void kmp1()
{
int k=0;
for(int i=1;i<=bb;++i)
{
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i]) ++k;
if(k==aa)
{
++ss;
if(ss>1000)
ss=1000;
else
q.push_back(i);
}
}
}
void kmp()
{
int k=0;
for(int i=2;i<=aa;++i)
{
while(k && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i]) ++k;
pi[i]=k;
}
}
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fscanf(f,"%s",a+1);
fscanf(f,"%s",b+1);
aa=strlen(a+1);
bb=strlen(b+1);
kmp();
kmp1();
fprintf(g,"%d\n",ss);
while(!q.empty())
{
int shh=q.front();
fprintf(g,"%d ",shh-aa);
q.pop_front();
}
fclose(f);
fclose(g);
return 0;
}