Cod sursa(job #2391083)

Utilizator AndreiStrAndrei Stroici AndreiStr Data 28 martie 2019 17:30:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 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 n,m,pr[N],nrPotriviri;
void prefix(),kmp();
vector<int> sol;
int main()
{
    char *p=a+1,*q=b+1;
    f>>p>>q;
    n=strlen(p);
    m=strlen(q);
    prefix();
    kmp();
    g<<nrPotriviri<<'\n';
    for(auto it:sol)
        g<<it<<' ';
    return 0;
}
void prefix()
{
    int q=0;
    for(int i=2;i<=n;i++)
    {
        while(q>0&&a[q+1]!=a[i])q=pr[q];
        if(a[q+1]==a[i])q++;
        pr[i]=q;
    }
}
void kmp()
{
    int q=0;
    for(int i=1;i<=m;i++)
    {
        while(q>0&&a[q+1]!=b[i])q=pr[q];
        if(a[q+1]==b[i])q++;
        if(q==n)
        {
            nrPotriviri++;
            if(nrPotriviri<=1000)
                sol.push_back(i-n);
        }
    }
}