Cod sursa(job #753450)

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

#define min(a,b) (((a) > (b)) ? (a) : (b) )

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;
    in >> a >> b;

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

    int i = 0,pos = 0;
    long long unsigned int n = 0;

    while(i < b.size())
    {
        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())
        {
            if(n<1000)
                f.push_back(i-pos);
            pos = t[pos-1] + 1;
            ++n;
        }
        else
            pos = t[pos];
    }
    out <<n<< "\n";
    for(i=0;i<min(f.size(),1000);++i)
        out << f[i]<< " ";
    return 0;
}