Cod sursa(job #2532044)

Utilizator CriviCriveanu Bogdan Crivi Data 27 ianuarie 2020 10:28:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in;
ofstream out;

string pat,s;
vector<int> ap,sol;

void pattern()
{
    ap.push_back(0);
    int z=1,nr=0;
    while(z<pat.size())
    {
        if(pat[z]==pat[nr])
        {
                nr++;
                ap.push_back(nr);
                z++;
        }
        else
        {
            if(nr==0)
            {
                ap.push_back(0);
                z++;
            }
            else
                nr=ap[nr-1];
        }
    }
}

void KMP()
{
    int n=s.size();
    int j=0, i=0;
    while (j<n)
    {
        if(s[j]==pat[i])
        {
            //int i=0;
                i++;
                j++;
        }
        if(i==pat.size())
        {
            sol.push_back(j-i);
            i=ap[i-1];
        }
        else if(j<n and pat[i]!=s[j])
        {
            if(i!=0)
                i=ap[i-1];
            else
                j++;
        }
    }
}

int main()
{
    in.open("strmatch.in");
    out.open("strmatch.out");
    
    in>>pat>>s;
    pattern();
    KMP();
    out<<sol.size()<<endl;
    for(int i=0;i<sol.size();i++)
        out<<sol[i]<<" ";
    return 0;
}