Cod sursa(job #2132809)

Utilizator sulzandreiandrei sulzandrei Data 16 februarie 2018 01:46:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <list>
#include <array>
#include <vector>
#include <string>
using namespace std;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
int * getPrefix(string& P)
{
    int m = P.size()-1;
    int* pi = new int[m+1]{};
    pi[1]=0;
    int k = 0;
    for(int q = 2 ; q<= m ; q++)
    {
        while(k>0 && P[k+1]!= P[q])
            k = pi[k];
        if(P[k+1] == P[q])
            k++;
        pi[q] = k;
    }
    return pi;
}
void kmp(string& T, string& P, vector<int>& res)
{

    int n = T.size()-1;
    int m = P.size()-1;

   int* pi = getPrefix(P);

    int q = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        while(q>0 && P[q+1] != T[i])
            q = pi[q];
        if(P[q+1] == T[i])
            q++;
        if(q == m)
        {
            res.push_back(i-m);
            q = pi[q];
        }
    }
}
int main()
{
    string w,s;
    in >> w;
    in >> s;
    vector<int> P;
    w.resize(w.size()+1);
    for(int i = w.size()-1; i>=0 ; i--)
        w[i+1] = w[i];
    s.resize(s.size()+1);
    for(int i =  s.size()-1; i>=0 ; i--)
        s[i+1] = s[i];
    if(w.size()<=s.size())
        kmp(s,w,P);
    out << P.size()<<'\n';
    int sz =(P.size()<1000?P.size():1000);
    for(int i = 0 ; i< sz ; i++)
        out<<P[i]<<" ";
    return 0;
}