Cod sursa(job #1556931)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 26 decembrie 2015 13:56:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstring>
#define nmax 2000005
#include <cstdio>

using namespace std;

int n,m,rez = 0;
char N[nmax],M[nmax];
int prefix[nmax],poz[nmax];

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    N[0] = M[0] = ' ';
    scanf("%s",N+1);
    scanf("%s",M+1);
    n = strlen(N);
    m = strlen(M);
    int k = 0,i;

    for(i = 2;i < n;++i){
        while(k && N[k+1] != N[i])k = prefix[k];
        if(N[i] == N[k+1])k++;
        prefix[i] = k;
    }
    k = 0;
    for(i = 1;i < m;++i){
        while(k && N[k+1] == M[i])k = prefix[k];
        if(N[k+1] == M[i])k++;
        if(k == n-1){
            rez++;
            if(rez<=1000)poz[rez] = i-n+1;
        }
    }
    printf("%d\n",rez);
    if(rez>1000)rez = 1000;
    for(i = 1;i<=rez;++i)printf("%d ",poz[i]);
    printf("\n");
 return 0;
}