Cod sursa(job #2107020)

Utilizator MithrilBratu Andrei Mithril Data 16 ianuarie 2018 17:58:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

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

int* precalc(string pattern)
{
    int* lsp = new int[pattern.size()];
    lsp[0]=0;
    for(int i=1;i<pattern.size();i++)
    {
        if(lsp[i-1]==0)
        {
            if(pattern[i]==pattern[0])
            {
                lsp[i]=1;
            }
            else
            {
                lsp[i]=0;
            }
        }
        else
        {
            if(pattern[i]==pattern[lsp[i-1]])
            {
                lsp[i]=lsp[i-1]+1;
            }
            else
            {
                lsp[i]=0;
            }
        }
    }
    return lsp;
}

vector<int> kmp(string pattern, string txt)
{
    int* lps = precalc(pattern);
    vector<int> sol;
    int i=0,m=0;
    for(;m<txt.size();)
    {
        if(i==pattern.size())
        {
            sol.push_back(m);
            m=m+1;
            i=0;
            continue;
        }
        if(txt[m+i]==pattern[i])
        {
            i++;
        }
        else
        {
            if(lps[i]==0)
            {
                i=0;
                m++;
            }
            else
            {
                m=m+lps[i];
                i=0;
            }
        }
    }
    return sol;
}

int main()
{
    string pat,txt;
    fin>>pat>>txt;
    vector<int> sol = kmp(pat, txt);
    fout<<sol.size()<<'\n';
    for(auto x:sol) fout<<x<<' ';
    return 0;
}