Cod sursa(job #2909779)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 15 iunie 2022 18:19:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define Nmax 2000005

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char p[Nmax], s[Nmax];
int pi[Nmax];
int main()
{
    fin >> p;
    fin >> s;

    ///prefix function
    int n=strlen(p);
    for(int i=1;i<n;i++)
    {
        int k=pi[i-1];
        while(k>0 && p[k]!=p[i])
            k=pi[k-1];
        if(p[k]==p[i])
            k++;
        pi[i]=k;
    }

    ///matching
    int k=0, m=strlen(s);
    vector <int> sol;
    for(int j=0;j<m;j++)
    {
        while(k>0 && p[k]!=s[j])
            k=pi[k-1];
        if(s[j]==p[k])
            k++;

        if(k==n)
            sol.push_back(j-n+1);
    }

    fout << sol.size() << '\n';
    if(sol.size()>1000) sol.resize(1000);
    for(auto it:sol)
        fout << it << ' ';
    return 0;
}