Cod sursa(job #940765)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 17 aprilie 2013 01:05:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int n, m, nrsol;
char a[2000010], b[2000010];
int pi[2000010];/// d[2000010];
vector <int> sol;

inline void Read()
{
    ifstream f("strmatch.in");
    f>>(a+1);
    f>>(b+1);
    f.close();
}

inline void prefix_PI()
{
    pi[1] = 0;
    int k = 0;
    for (int i = 2; i<=n; i++)
    {
        while (k && a[k+1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            k++;
        pi[i] = k;
    }
}

inline void Solve()
{
    n = strlen (a+1);
    m = strlen (b+1);
    prefix_PI();
    int i, k = 0;
    for (i=1; i<=m; i++)
    {
        while (k && a[k+1] != b[i])
            k = pi[k];
        if (a[k+1] == b[i]) // s-au potrivit literele;
            k++;
        /// d[i] = k;
        if (k == n)
        {
            nrsol++;
            if (nrsol <= 1000)
                sol.push_back(i-n);
            k = pi[k];
        }
    }
}

inline void Write()
{
    ofstream g("strmatch.out");
    g<<nrsol<<"\n";
    for (vector<int>::iterator it = sol.begin(); it!=sol.end(); it++)
        g<<*it<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}