Mai intai trebuie sa te autentifici.

Cod sursa(job #2039698)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 14 octombrie 2017 19:59:18
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>

using namespace std;

char w[2000005],s[2000005];
int t[2000005];
int sol[2000005],soll=0;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    int lw,ls;

    scanf("%s",w+1);
    scanf("%s",s+1);

    t[0]=-1;
    t[1]=0;

    lw=strlen(w+1);

    for(int i=2;i<=lw;++i)
    {
        int k=i-1;
        while(t[k]!=-1&&w[t[k]+1]!=w[i])
            k=t[k];
        t[i]=t[k]+1;
    }

    ls=strlen(s+1);
    int wi=1;
    int si=0;

    while(si+wi<=ls)
    {
        if(w[wi]==s[si+wi])
        {
            wi++;
            if(wi==lw+1)
            {
                wi--;
                ++soll;
                sol[soll]=si;
                si=si+wi-t[wi];
                wi=t[wi]+1;
            }
        }
        else
        {
            if(t[wi]>0)
            {
                si=si+wi-t[wi];
                wi=t[wi]+1;
            }
            else
            {
                si=si+wi;
                wi=1;
            }
        }
    }

    printf("%d\n",soll);
    if(soll>=1000)
        soll=1000;
    for(int i=1;i<=soll;++i)
        printf("%d ",sol[i]);

    return 0;
}