Cod sursa(job #2865086)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 8 martie 2022 14:52:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,a;
int lps[2000011],i,j,n,m,S;
vector <int> sol;
void lpsbuild()
{
    int i=1,j=0;
    while(i<n)
    {
        if(a[i]==a[j])
        {
            j++;
            lps[i]=j;
            i++;
        }
        else
        if(j==0)
        {
            lps[i]=0;
            i++;
        }
        else
            j=lps[j-1];
    }
}
void kmp()
{
    int i=0,j=0;
    while(i<n)
    {
        if(A[i]==a[j])
        {
            i++;
            j++;
            if(j==m)
            {
            S++;
            if(S<=1000)
                sol.push_back(i-m);
            j=lps[j-1];
            }
        }
        else
        if(j==0)
            i++;
        else
            j=lps[j-1];
    }
}
int main()
{
    f>>a;
    f>>A;
    m=a.size();
    n=A.size();
    lpsbuild();
    kmp();
    g<<S<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i]<<" ";
    return 0;
}