Cod sursa(job #1402247)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 26 martie 2015 13:45:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <string>
#define DMAX 2000050
using namespace std;

 char P[DMAX],T[DMAX];
long  urm[DMAX];
vector<long> solutii;
int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in >> P >> T;
    long long n,m,k,x;
    n=strlen(T),m=strlen(P);
    //cout << n << " " << m;
    k=-1,x=0;
    urm[0]=0;
    for(x=1;x<m;x++)
    {
        while(k>0 && P[k+1]!=P[x]) k=urm[k];
        if(P[k+1]==P[x]) k++;
        urm[x]=k;
    }
    x=-1;

    for(long long i=0;i<n;i++)
    {
        while(x>0 && P[x+1]!=T[i]) x=urm[x];
        if(P[x+1]==T[i]) x++;
        if(x==m-1)
        {
            solutii.push_back(i-m+1);
            x=urm[x];
        }
    }
    int nr=1000;
    if(solutii.size()<1000) nr=solutii.size();
    out << solutii.size() << "\n";
    for(long long i=0;i<nr;i++)
        out << solutii[i] <<  " ";

    return 0;
}