Cod sursa(job #927286)

Utilizator RaduDoStochitoiu Radu RaduDo Data 25 martie 2013 18:28:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define nMax 2000010
#define mMax 2000010
using namespace std;
vector <int> sol;

int Urm[mMax];
char T[nMax], P[mMax];
int n, m;

int min(int a, int b)
{
    if(a<b) return a;
    return b;
}

void Urmatorul(char *P)
{
    int k=-1, x;
    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;
    }
}

int main()
{
    int i, x=-1;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(P);    gets(T);
    n=strlen(T);    m=strlen(P);
    Urmatorul(P);
    for(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)
        {
            sol.push_back(i-m+1);
            x=Urm[x];
        }
    }
    printf("%d\n",sol.size());
    for(i=0; i<min(sol.size(),999); ++i)
        printf("%d ",sol[i]);
    return 0;
}