Cod sursa(job #1889689)

Utilizator codebreaker24Tivadar Ionut codebreaker24 Data 22 februarie 2017 20:44:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

vector<int> searchKMP(string txt, string pat);
vector<int> computeV(string pat);

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

int main ()
{

        string txt;
        string pat;
        vector<int> sol;
        int n, i;
        fin >> pat >> txt;
        sol =  searchKMP(txt,pat);

        n = sol.size();
        fout << n << '\n';

        for(i=0; i<n; i++)
            fout << sol[i] << ' ';

}


vector<int> searchKMP(string txt, string pat)
{
        int M = pat.size();
        int N = txt.size();
        vector<int> V = computeV(pat);
        vector<int> sol;
        int i=0;
        int j=0;
        while( i< N)
        {
            if(pat[j] == txt[i])
            {
                i++;
                j++;
            }
            if(j == M)
            {
                sol.push_back(i-M);
                j = V[j-1];
            }
            else
                if(i <N &&pat[j] != txt[i])
                {
                    if(j!=0)
                       j = V[j-1];
                    else
                        i++;

                }

        }
        return sol;

}

vector<int> computeV(string pat)
{
        int M = pat.size();
        vector<int> V(M, 0);
        V[0] = 0;
        int i= 1;
        int len = 0;

        while(i < M)
        {
            if(pat[i] == pat[len])
            {
                len++;
                V[i] = len;
                i++;
            }

                else
                    if(len != 0)
                        len = V[len -1];
                    else
                        {
                            V[i] = 0;
                            i++;
                        }


        }
        return V;
}