Cod sursa(job #2980528)

Utilizator Andrei_Gagea08Andrei Gagea Andrei_Gagea08 Data 16 februarie 2023 16:37:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
/// strmatch de pe infoarena cu KMP

#include <fstream>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char v[4000002];
int pi[4000002];
long long sol[1001];

int main()
{
    long long n=0,i=0,l,nrap=0;
    char ch;
    cin.get(ch);
    while(ch!='\n')
    {
        v[++n]=ch;
        cin.get(ch);
    }
    l=n;
    n++;
    v[n]='#';
    for(i=2;i<n;i++)
    {
        pi[i]=pi[i-1];
        while(pi[i]!=0 && v[pi[i]+1]!=v[i])
        {
            pi[i]=pi[pi[i]];
        }
        if(v[pi[i]+1]==v[i])
            pi[i]++;
    }
    i=n;
    pi[n]=0;
    n++;
    while(cin.get(v[n]))
    {
        i++;
        pi[i]=pi[i-1];
        while(pi[i]!=0 && v[pi[i]+1]!=v[n])
        {
            pi[i]=pi[pi[i]];
        }
        if(v[pi[i]+1]==v[n])
            pi[i]++;
        if(pi[i]==l)
        {
            nrap++;
            if(nrap<=1000)
                sol[nrap]=i-1LL*l-1LL*l-1;
        }
        n++;
    }
    n-=2;
    cout<<nrap;
    cout<<'\n';
    for(i=1;i<=nrap && i<=1000;i++)
        cout<<sol[i]<<" ";
    cout<<'\n';
    return 0;
}