Pagini recente » Cod sursa (job #3313035) | Monitorul de evaluare | Cod sursa (job #2591379) | Cod sursa (job #3311231) | Cod sursa (job #1915545)
#include <iostream>
#include <cstdio>
#include <cstring>
#define lim 1000
using namespace std;
const int NMax = 2000005;
char pattern[NMax], sir[NMax];
int pi[NMax];
int lenp, lens;
void Prefix()
{
pi[1]=0;
int j=0;
for(int i=2; i<=lenp; ++i)
{
while(j>=1 && pattern[i]!=pattern[j+1])
j=pi[j];
if(pattern[j+1]==pattern[i])
++j;
pi[i]=j;
}
}
int matches;
int match[NMax];
void KMP()
{
int j=0;
for(int i=1; i<=lens; ++i)
{
while(j>=1 && pattern[j+1]!=sir[i])
j=pi[j];
if(sir[i]==pattern[j+1])
++j;
if(j == lenp)
{
++matches;
if(matches <= lim)
match[matches]=i-lenp;
}
}
printf("%d\n", matches);
for(int i=1; i<=min(matches, lim); ++i)
printf("%d ", match[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", &pattern);
scanf("%s", &sir);
lenp=strlen(pattern);
lens=strlen(sir);
for(int i=lenp; i>=1; --i)
pattern[i]=pattern[i-1];
for(int i=lens; i>=1; --i)
sir[i]=sir[i-1];
Prefix();
KMP();
return 0;
}