Cod sursa(job #1469407)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 8 august 2015 10:51:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "strmatch.in";
const char oname[] = "strmatch.out";
int N;
int poz[1005];
ofstream out(oname);
string P, T;
vector<int> getPrefixFunction(const string P)
{
    int m  = P.length();
    vector<int> pr;
    pr.push_back(-1);
    int k = -1;
    for(int q = 1; q < m; q++)
    {
        while(k >= 0 && P[k+1] != P[q])
            k = pr[k];
        if(P[k+1] == P[q])
            k++;
        pr.push_back(k);
    }
    return pr;
}

void KMP_Matcher(const string T, const string P)
{
    int m = P.length();
    int t = T.length();
    vector<int> pr = getPrefixFunction(P);
    int q = -1;
    for(int i = 0; i < t; i++)
    {
        while(q > -1 && P[q+1] != T[i]) q = pr[q];
        if(P[q+1] == T[i])  q++;
        if(q == m-1)
        {
            if(N<1000)
                poz[N] = i - m +1;
            N++;
            q = pr[q];
        }
    }
    out << N << '\n';
    for(int i = 0; i < N && i < 1000; i++)
        out << poz[i] << ' ';
}

int main()
{
    ifstream in(iname);
    in >> P >> T;
    KMP_Matcher(T,P);
    return 0;
}