Cod sursa(job #2229877)

Utilizator cezarzbughinCezar Zbughin cezarzbughin Data 8 august 2018 12:22:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 2000010;
char a[N],b[N];
int na,nb,cnt,p[N],sol[1010];
void prefix(),KMP();

int main()
{
    f>>(a+1)>>(b+1);
    prefix();
    KMP();
    g<<cnt<<'\n';
    cnt=min(cnt,1000);
    for(int i=1;i<=cnt;i++)
        g<<sol[i]<<' ';
    return 0;

}

void prefix()
{
    na=strlen(a+1);
    int q=0;
    for(int i=2; i<=na; i++)
    {
        while(q&&a[i]!=a[q+1])q=p[q];
        if(a[i]==a[q+1])q++;
        p[i]=q;
    }
}

void KMP()
{
    nb=strlen(b+1);
    int q=0;
    for(int i=1; i<=nb; i++)
    {
        while(q&&b[i]!=a[q+1])q=p[q];
        if(b[i]==a[q+1])q++;
        if(q==na)
        {
            cnt++;
            if(cnt<=1000)
                sol[cnt]=i-na;
        }
    }
}