Pagini recente » Cod sursa (job #2667598) | Cod sursa (job #2745064) | Cod sursa (job #2380178) | Cod sursa (job #1344377) | Cod sursa (job #783792)
Cod sursa(job #783792)
#include<cstdio>
#include<queue>
#include<vector>
#define P 699997
#define MAXN 2000001
using namespace std;
typedef unsigned int nat;
char a[MAXN],b[MAXN];
vector<nat>pi(MAXN);
queue<nat> rez;
int main()
{
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
nat na,nb,i,k=0,n=0;
char aux1,aux2;
fscanf(f,"%s",a);
fscanf(f,"%s",b);
na=strlen(a);
nb=strlen(b);
aux1=a[0];
for(i=1;i<=na;++i)
{
aux2=a[i];
a[i]=aux1;
aux1=aux2;
}
aux1=b[0];
for(i=1;i<=nb;++i)
{
aux2=b[i];
b[i]=aux1;
aux1=aux2;
}
/*while(fscanf(f,"%c",aux1))
a[++na]=aux1;
while(fscanf(f,"%c",aux1))
b[++nb]=aux1;*/
pi[1]=0;
for(i=2;i<=na;i++)
{
while(k && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
++k;
pi[i]=k;
}
k=0;
for(i=1;i<=nb;i++)
{
while(k && b[i]!=a[k+1])
k=pi[k];
if(b[i]==a[k+1])
++k;
if(k==na)
{
++n;
if(n<1000)
rez.push(i-na);
}
}
fprintf(g,"%u\n",n);
while(!rez.empty())
fprintf(g,"%u ",rez.front()),rez.pop();
fclose(f);
fclose(g);
return 0;
}