Cod sursa(job #1552517)

Utilizator andru47Stefanescu Andru andru47 Data 18 decembrie 2015 11:04:04
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
/*
v1 = B M
v2 = A N
construiesc phi pt A
for(i=1; i<=m; ++i)
{
    k=v[i-1];
    while(k>0&&b[i]!=a[k+1])
    {
        k=phi[k];
    }
    if (b[i]==a[k+1])v[i]=k+1;
        else v[i]=0;
}

*/
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000000 + 5;
int phib[NMAX],phia[NMAX];
char a[NMAX],b[NMAX];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1);
    gets(b+1);
    phia[1]=0;
    int len1=strlen(a+1);
    int len2=strlen(b+1);
    int k;
    for (int i = 2; i<=len1; ++i)
    {
        k = phia[i-1];
        while(k>0&&a[k+1]!=a[i])
        {
            k=phia[k];
        }
        if (a[i]==a[k+1])phia[i]=k+1;
        else  phia[i]=0;
    }
    for (int i = 1; i<=len2; ++i)
    {
        k=phib[i-1];
        while(k>0&&b[i]!=a[k+1])
        {
            k=phia[k];
        }
        if (b[i]==a[k+1])phib[i]=k+1;
        else phib[i]=0;
    }
    int nr = 0 ;
    for (int i = 1; i<=len2; ++i)
    {
        if (phib[i]==len1)
            ++nr;
    }
    printf("%d\n",nr);
    int x = 1000;
    for (int i = 1; i<=len2 && x>0; ++i,--x)
    {
        if (phib[i]==len1)
        {
            printf("%d ",i-len1);
        }
    }
    printf("\n");
    return 0;
}