Pagini recente » Cod sursa (job #2847916) | Cod sursa (job #1260528) | Cod sursa (job #2263471) | Cod sursa (job #2565086) | Cod sursa (job #2882155)
//Ilie Dumitru
#include<cstdio>
#include<cstring>
typedef long long int ll;
const int NMAX=2000005;
char pattern[NMAX], text[NMAX];
int N/*pattern*/, M/*text*/;
int pi[NMAX];
int nrAp, ans[1000];
void prefix()
{
int i, k;
pi[0]=0;
pi[1]=0;
for(i=2, k=0;i<=N;++i)
{
while(k && pattern[k]!=pattern[i-1])
k=pi[k];
if(pattern[k]==pattern[i-1])
pi[i]=++k;
}
//for(i=0;i<N;++i)
// printf("%c %d\n", pattern[i], pi[i+1]);
}
void match()
{
int q, i;
for(q=0, i=0;i<M;++i)
{
while(q && pattern[q]!=text[i])
q=pi[q];
if(pattern[q]==text[i])
++q;
if(q==N)
{
if(nrAp<1000)
ans[nrAp]=i-N+1;
++nrAp;
}
}
}
int main()
{
int i;
FILE* f=fopen("strmatch.in", "r"), *g=fopen("strmatch.out", "w");
fgets(pattern, NMAX, f);
fgets(text, NMAX, f);
N=strlen(pattern);
if(pattern[N-1]=='\n')
pattern[--N]=0;
M=strlen(text);
if(text[M-1]=='\n')
text[--M]=0;
prefix();
match();
fprintf(g, "%d\n", nrAp);
for(i=0;i<nrAp && i<1000;++i)
fprintf(g, "%d ", ans[i]);
fclose(f);
fclose(g);
return 0;
}