Cod sursa(job #2803251)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 19 noiembrie 2021 18:31:02
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,nr,m;
int rez[2000005],urmator[2000005],v[2000005];
string s,pat;
void init()
{
    int i,j;
    urmator[0]=-1;
    for(i=1; i<n; i++)
    {
        j=urmator[i-1];
        while(j>=0&&pat[i]!=pat[j])
            j=urmator[j];
        if(j==-1)
        {
            if(pat[i]==pat[0])urmator[i]=0;
            else urmator[i]=-1;

        }
        else urmator[i]=j+1;
    }
}

void kmp()
{
    n=pat.size();
    m=s.size();
    init();
    urmator[0]=0;
    int i,j;
    int x;
    v[0]=(s[0]==pat[0]?0:-1);

    for(i=1; i<m; i++)
    {
        x=v[i-1];


        while(x!=-1&&s[i]!=pat[x+1])
            x=urmator[x];

        if(x==-1)
        {
            if(s[i]==pat[0]) v[i]=0;
            else v[i]=-1;
        }
        else
            v[i]=x+1;

        if(v[i]==n-1)
            rez[++nr]=i+1-n;
    }
    fout<<nr<<'\n';
    for(i=1; i<=nr; i++)
    {
        fout<<rez[i]<<" ";
    }
}
int main()
{
    fin>>pat;
    fin.get();

    fin>>s;
    kmp();
    return 0;
}