Cod sursa(job #1974677)

Utilizator raulmuresanRaul Muresan raulmuresan Data 28 aprilie 2017 14:26:47
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<vector>
#include<string>
#define modulo 666013

using namespace std;

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

const int NMAX = 2000005;

string a, b;
int i, n, k, j,contor,st,dr,x,y;
int prefix[NMAX];
vector<int> sol;

void build_prefix()
{
    prefix[0] = 0;
    int k = -1;
    for(int i = 1; i < a.length(); i++)
    {
        while(k > 0 && a[k + 1] != a[i])
        {
            k = prefix[k];
        }
        if(a[k + 1] == a[i])
        {
            k++;
        }
        prefix[i] = k;

    }
    for(i = 0; i < a.length(); i++)
    {
        //fout << prefix[i] << " ";
    }

}

int main()
{
    fin >> a >> b;
    //fout << a <<"\n"<<b <<"\n";

    build_prefix();
    int m = a.length();


    int k = -1;
    for(int i = 0; i < b.length(); i++)
    {
        while(k > 0 && a[k + 1] != b[i])
        {
            k = prefix[k];
        }
        if(a[k + 1] == b[i])
        {
            k++;
        }
        if(k == m - 1)
        {
            //fout << i - m + 1 << "\n";
            sol.push_back(i - m + 1);
            k = prefix[k];
        }
        prefix[i] = k;

    }

    if(sol.size() > 1000 ) contor = 1000;
    else contor = sol.size();



    fout << sol.size() << "\n";
    for(i = 0; i < contor;i++)
    {
        fout << sol[i] <<" ";
    }


}