Cod sursa(job #2007994)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 4 august 2017 20:23:01
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int maxn = 2000005;
vector <int> sol;
int pi[maxn * 2];
int main()
{
    string a, b;
    in >> a >> b;
    //a = " " + a;
    b = a + b;
    b = " " + b;
    int x = 0;
    for(unsigned int i = 2; i < b.size(); i++)
    {
        while(x > 0 && b[i] != b[x + 1])
            x = pi[x];
        if(b[x + 1] == b[i])
        {
            x++;
            pi[i] = x;
        }
        else
            pi[i] = x;
    }
    //for(unsigned int i = 1; i < b.size(); i++)
    //    cerr << pi[i] << " ";
    //cerr << a << " ";
    for(unsigned int i = 1; i < b.size(); i++)
        if(pi[i] >= (int)a.size())
            sol.push_back(i - 2 * a.size());
    out << sol.size() << "\n";
    for(int i = 0; i <= min(999, (int)sol.size() - 1); i++)
        out << sol[i] << " ";
    out << "\n";
    return 0;
}