Cod sursa(job #1659740)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 22 martie 2016 16:00:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,pi[2000010],v[1001],h;
char s1[2000010],s2[2000010];
void prefix()
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        while(p&&s1[i]!=s1[p+1])p=pi[p];
        if(s1[i]==s1[p+1])p++;
        pi[i]=p;
    }
}
void kmp()
{
    int p=0;
    prefix();
    for(int i=1;i<=m;i++)
    {
        while(p&&s2[i]!=s1[p+1])p=pi[p];
        if(s2[i]==s1[p+1])p++;
        if(p==n)if(++h<=1000)v[h]=i-n;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(s1+1,2000010,stdin);
    fgets(s2+1,2000010,stdin);
    n=strlen(s1+1)-1;
    m=strlen(s2+1)-1;
    kmp();
    printf("%d\n",h);
    if(h>1000)h=1000;
    for(int i=1;i<=h;i++)
        printf("%d ",v[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}