Cod sursa(job #2277175)

Utilizator zhm248Mustatea Radu zhm248 Data 5 noiembrie 2018 20:54:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000001],b[2000001];
int k[2000001],ap[1001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s\n",a+1,b+1);
    int na=strlen(a+1),nb=strlen(b+1),i,val=0,nr=0;
    for(i=2;i<=na;++i)
    {
        while(val&&a[i]!=a[val+1])
        {
            val=k[val];
        }
        if(a[i]==a[val+1])
        {
            val++;
            k[i]=val;
        }
        else
            k[i]=0;
    }
    val=0;
    for(i=1;i<=nb;++i)
    {
        while(val&&a[val+1]!=b[i])
        {
            val=k[val];
        }
        if(b[i]==a[val+1])
            val++;
        if(val==na)
        {
            nr++;
            if(nr<=1000)
                ap[nr]=i-na;
        }
    }
    printf("%d\n",nr);
    for(i=1;i<=nr&&i<=1000;++i)
    {
        printf("%d ",ap[i]);
    }
    return 0;
}