Cod sursa(job #1402005)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 26 martie 2015 11:45:17
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define DMAX 2000005
using namespace std;

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

    in >> P >> T;
    int n,m,k,x;
    n=strlen(T),m=strlen(P);

    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(int 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(int i=0;i<nr;i++)
        out << solutii[i] <<  " ";
    return 0;
}