Cod sursa(job #1468959)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 7 august 2015 13:06:53
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
const char iname[] = "strmatch.in";
const char oname[] = "strmatch.out";

bool suffix(const string &P, int k,const int &i, const char &c)
{
    string S;
    S.assign(P,0,i);
    S+=c;
    k--;
    for(int j = S.length() - 1 ; k >= 0 && j>=0; k--, j--)
    {
        if(P[k]!= S[j])
            return false;
    }
    return true;
}
int Match(const string &T, int it, const vector<vector<int> > &delta)
{
    int x = T.length();
    int y = delta.size();
    for(int  q = 0; it < x; ++it)
    {
        int r = ((T[it] - 'a' < 0) ? T[it] - 'A' + 26 : T[it] - 'a');
        if(r < 0) r = 52;
//        cout << T[it] << ' ' << r << '\n';
        q = delta[q][r];
        if(q == y)   return it;
    }
    return -1;
}
void Create_delta(const string &P, const string &Sigma, vector<vector<int> > &delta)
{
    int p = P.length();
    for(int i = 0; i < p; i++)
    {
        int s = Sigma.length();
        vector<int> dummy;
        delta.push_back(dummy);
        for(int j = 0; j < s; j++)
        {
            int k = min(p+1, i+2);
            do
            {
                k--;
            }while(!suffix(P,k,i,Sigma[j]));
            (delta[i]).push_back(k);
        }
    }
}
int main()
{
    int a[1005],p,t;
    a[0] = 0;
    ifstream in(iname);
    ofstream out(oname);
    vector< vector<int> > delta;
    string P = "ABA", T = "CABBCABABABA";
    string Sigma = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    in >> P >> T;
    p = P.length();
    t = T.length();
    Create_delta(P,Sigma,delta);
    int q = 0;
    do{
        if(q == 0)
            q = Match(T, 0,delta);
        else
            q = Match(T, q-p+2, delta);
        if(q > 0)
        {
            ++a[0];
            if(a[0] < 1005)
                a[a[0]] = q - p + 1;

        }
    }while(q >= 0 && q < t);
    out << a[0] << '\n';
    for(int i = 1; i <= a[0] && i < 1001; i++)
        out << a[i] << ' ';
    return 0;
}