Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #1078867) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #766926)
Cod sursa(job #766926)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 2000002
char a[MAX],b[MAX];
int u[MAX],c[1001],n,m,nr = 0;
void prefix(){
int k = 0;
for(int i=2;i<=n;i++)
{
while( k > 0 && a[k+1] != a[i] )k = u[k];
if( a[k+1] == a[i] )k++;
u[i] = k;
}
}
void kmp(){
int k = 0;
for(int i=1;i<=m;i++)
{
while( k > 0 && a[k+1] != b[i] )k = u[k];
if( a[k+1] == b[i] )k++;
if( k == n )
{
nr++;
if( nr <= 1000 )c[nr] = i - k;
k = u[k];
}
}
printf("%d\n",nr);
for(int i=1;i<=min( nr, 1000 );i++) printf("%d ",c[i]);
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s ",a);
scanf("%s ",b);
n = strlen(a);
m = strlen(b);
for(int i=n;i>0;i--)a[i] = a[i-1];
for(int i=m;i>0;i--)b[i] = b[i-1];
prefix();
kmp();
return 0;
}