Cod sursa(job #1631842)

Utilizator T.C.11Tolan Cristian T.C.11 Data 5 martie 2016 19:23:07
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,m,i,k,nr;
int pi[2000002];
char w[2000002],t[2000002];

vector<int> v;

int main()
{
    fin>>w>>t;
    n = strlen(w);
    m = strlen(t);
    for (i=n;i>=1;i--)
        w[i] = w[i-1];
    w[0] = 0;
    for (i=m;i>=1;i--)
        t[i] = t[i-1];
    t[0] = 0;

    k = 0;
    for (i=2;i<=n;i++)
    {
        if (k > 0 && w[k+1] != w[i])
            k = pi[k];
        if (w[k+1] == w[i])
            k++;
        pi[i] = k;
    }

    k = 0;
    for (i=2;i<=m;i++)
    {
        if (k > 0 && w[k+1] != t[i])
            k = pi[k];
        if (w[k+1] == t[i])
            k++;
        if (k == n)
        {
            if (nr < 1000)
            {
                nr++;
                v.push_back(i - n);
            }
        }
    }

    fout<<nr<<"\n";
    for (i=0;i<nr;i++)
        fout<<v[i]<<" ";
    return 0;
}