Cod sursa(job #2132805)

Utilizator sulzandreiandrei sulzandrei Data 16 februarie 2018 01:26:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 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");
vector<int> getPrefix(string P)
{
    int m = P.size()-1;
    vector<int> pi(m+1,0);
    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();
    int m = P.size();
    T.resize(n+1);
    P.resize(m+1);
    for(int i = T.size()-1; i>0 ;i--)
        T[i+1] = T[i-1];
    for(int i = P.size()-1; i>0 ;i--)
        P[i+1] = P[i-1];
    vector<int> pi = getPrefix(P);

    int q = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        while(q>0 && P[q+i] == 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 a,b;
    in >> a;
    in >> b;
    vector<int> P;
    kmp(b,a,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;
}