Cod sursa(job #753438)

Utilizator ericptsStavarache Petru Eric ericpts Data 29 mai 2012 21:29:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;

void form_t(vector <int> & t,string s)
{
    int i,pos = 0;
    for(i=1;i<t.size();++i)
    {
        t[i] = pos;
        if(s[i] == s[pos])
            ++pos;
        else
            pos = 0;
    }
}


int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    string a,b;
    getline(in,a);
    getline(in,b);

    vector <int> t (a.length(),0);
    vector <int> f ;
    form_t(t,a);

    int i = 0,pos = 0;

    while(i < b.size() && f.size() < 1000)
    {
        if(pos == 0)
        {
            while(b[i] != a[0] && i < b.size())
                ++i;
        }
        while(b[i] == a[pos] && i < b.size() && pos < a.size())
        {
            ++i;
            ++pos;
        }
        if(pos == a.size())
        {
            f.push_back(i-pos);
            pos = t[pos-1] + 1;
        }
        else
            pos = t[pos];
    }
    out << f.size() << "\n";
    for(i=0;i<f.size();++i)
        out << f[i]<< " ";
    return 0;
}