Cod sursa(job #1998712)

Utilizator dumitrescu_andreiDumitrescu Andrei dumitrescu_andrei Data 8 iulie 2017 20:57:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;


char A[2000005],B[2000005];
int N,M;
int urm[2000005];
int V[1024];
int w;

void urmatorul()
{
    int k=0;
    urm[1]=0;

    for(int x=2;x<=M;++x)
    {
        while(k>0 && A[k+1]!=A[x]) k=urm[k];
        if(A[k+1]==A[x]) k++;
        urm[x]=k;
    }


}

int main()
{ int x=0,i;

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);
    for (; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')
            || (A[M] >= '0' && A[M] <= '9'); ++M);
    for (; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')
            || (B[N] >= '0' && B[N] <= '9'); ++N);
    for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
    for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';

urmatorul();
for(int i=1;i<=N;++i)
{
    while(x>0 && A[x+1]!=B[i]) x=urm[x];
    if(A[x+1]==B[i]) x++;
    if(x==M)
    {
      ++w;
      if(w<=1000)
        V[w]=i-M;

        x=urm[M];
    }
}
 printf("%d\n", w);
    for (i = 1; i <= min(w, 1000); ++i)
        printf("%d ", V[i]);
    printf("\n");
return 0;
}