Cod sursa(job #1769722)

Utilizator sulzandreiandrei sulzandrei Data 3 octombrie 2016 00:17:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

ifstream in("grader_test24.in");
ofstream out("strmatch.out");
#define nr_char 256
bool PksuffixPqa(const string & P,int k,int q,int a)//O(m)
{
    if(k == -1)
        return true;
    if(P[k]!=a)         //
        return false;
    for(int i = k-1 ; i >= 0 ; i--,q--)
        if(P[i]!=P[q])
            return false;
    return true;
}
int** precomputeDeltaFunction(const string& P)//O(m^3*|sigma|)
{

    bool ok;

    int m = P.size(),k;

    int** delta = new int*[m+1];
    for(int i = 0 ; i <= m ; i++)
        delta[i] = new int[nr_char]{};

    for(int q = 0 ;  q <= m ; q++)//O(m)
        for(int a = 0 ; a < nr_char; a++)//O(m*|sigma|)
        {
            k = min(m+1,q+2);
            do
            {
                k--;
                ok = PksuffixPqa(P,k-1,q-1,a);//O(m^3*|sigma|)
            }
            while(!ok);//O(m^2 *|sigma|)
            delta[q][a] = k;
        }
    return delta;
}
void finiteStateAutomaton(const string& T,int** const delta,int m,vector<int>& pos)
{
    int n = T.size();
    if(m>n)
        return;
    int q = 0;
    for(int i = 0 ; i < n ; i++)
    {
        q = delta[q][(int)T[i]];
        if(q == m)
            pos.push_back(i-m+1);
    }
}
int * prefixFunction(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 matchKMP(string& T, string& P,vector<int>& pos)
{
    int n = T.size()-1;
    int m = P.size()-1;
    int * pi = prefixFunction(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)
        {
            pos.push_back(i-m);
            q = pi[q];
        }
    }
}
int main()
{
    vector<int> pos;
    string s,w;
    in >> w >> s;
    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];
    matchKMP(s,w,pos);
    //finiteStateAutomaton(s,precomputeDeltaFunction(w),w.size(),pos);

    out<<pos.size()<<'\n';
    for(int j = 0 ; j < std::min((int)pos.size(),1000); j++)
        out<<pos[j]<<" ";

    return 0;
}