Cod sursa(job #883596)

Utilizator RaduDoStochitoiu Radu RaduDo Data 20 februarie 2013 10:32:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 2000010
using namespace std;
int Urm[maxn];
char T[maxn],P[maxn];
int n,m,q,i,l;
vector < int > st;

void Urmatorul()
{
    int k,m,q;
    m=strlen(P)-1;
    Urm[1] = 0;
    k = 0;
    for(q=2; q<=m; ++q)
    /*determina lungimea celui mai lung prefix al lui P
        care este si sufix al subsirului P[1..q]*/
    {
    while (k>0 && P[k+1]!=P[q])
        k = Urm[k];
    if(P[k+1]==P[q])
        ++k;
    Urm[q] = k;
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(P+1); gets(T+1); P[0]=' '; T[0]=' ';
    n = strlen(T)-1;
    m = strlen(P)-1;
    Urmatorul();
    q = 0;
    for(i=1; i<=n; ++i)
    {
        while(q>0 && P[q+1]!=T[i]) q = Urm[q];
        if (P[q+1]==T[i])
            ++q; /*s-a mai gasit un caracter corect*/
        if (q==m)
        {
            st.push_back(i-m);
            q = Urm[q];
        }
    }
    l=st.size();
    printf("%d\n",l);
    for(i=0; i<l; ++i)
        printf("%d ",st[i]);
    return 0;
}