Cod sursa(job #2626670)

Utilizator bem.andreiIceman bem.andrei Data 7 iunie 2020 15:09:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
string a, b;
int p[2000005], n, m;
vector<int>f;
void pref()
{
    p[1]=0;
    int ans=0;
    for(int i=2; i<=n; i++)
    {
        while(ans!=0 && a[ans+1]!=a[i])
        {
            ans=p[ans];
        }
        if(a[ans]==a[i])
        {
            ans++;
        }
        p[i]=ans;
    }
}
void kmp()
{
    int i=0, j=0;
    while(j<m)
    {
        if(a[i]==b[j])
        {
            i++;
            j++;
        }
        if(i==n)
        {
            f.push_back(j-i);
            i=p[i-1];
        }
        else
        {
            if(j<m && a[i] != b[j])
            {
                if(i!=0)
                {
                    i=p[i-1];
                }
                else
                {
                    j++;
                }
            }
        }
    }
}
int main(void)
{
    r>>a;
    r>>b;
    n=a.size(), m=b.size();
    pref();
    kmp();
    w<<f.size()<<"\n";
    for(int i=0; i<f.size(); i++)
    {
        w<<f[i]<<" ";
    }
    return 0;
}