Pagini recente » Cod sursa (job #845956) | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1879562)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LENGTH_MAX 2000005
using namespace std;
char str[LENGTH_MAX];
char pattern[LENGTH_MAX];
int pi[LENGTH_MAX], M, N;
void Prefix()
{
int len=strlen(pattern);
pi[1]=0;
int k=0;
for(int q=2; q <= len; ++q)
{
while(k>0 && pattern[k+1]!=pattern[q])
k=pi[k];
if(pattern[k+1]==pattern[q])
++k;
pi[q]=k;
}
}
int potriv;
int poz[LENGTH_MAX];
void KMP()
{
int q=0;
for(int i=1; i<=N; ++i)
{
while(q>0 && pattern[q+1]!=str[i])
q=pi[q];
if(pattern[q+1]==str[i])
++q;
if(q==M)
{
++potriv;
if(potriv<=1000)
poz[potriv]=i-M;
else
break;
}
}
cout<<potriv<<"\n";
for(int i=1; i<=min(N,1000); ++i)
cout<<poz[i]<<" ";
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", &pattern);
scanf("%s", &str);
M=strlen(pattern);
N=strlen(str);
int i;
for (i = M; i; --i)
pattern[i] = pattern[i-1];
pattern[0] = ' ';
for (i = N; i; --i) str[i] = str[i-1];
str[0] = ' ';
pattern[M+1]=0;
str[N+1]=0;
Prefix();
KMP();
return 0;
}