Cod sursa(job #2288907)

Utilizator VictorasulVictor Bertalan Victorasul Data 24 noiembrie 2018 09:24:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define NMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char c[NMAX] , a[NMAX] ;
int k = 0 , p[NMAX] , i , nrsol = 0 , N , M , sol[NMAX] , x = 0;
int main()
{
    f >> c+1;
    f >> a+1;
    k = 0 ;
    N = strlen(c+1) ;
    M = strlen(a+1);
    for (i = 2 ; i <= N ; i++)
    {
      for (;k != 0 && c[k+1] != c[i];) k = p[k];
      if (c[k+1] == c[i]) k ++ ;
      p[i] = k ;
    }

    k = 0 ;
    for (i = 1 ; i <= M ; i ++)
    {
        for (;k != 0 && c[k+1] != a[i];) k = p[k];
        if (c[k+1] == a[i]) k ++ ;
        if (k == N) {nrsol ++ ; x ++ ;
        sol[x] = i - N; }
    }
    g << nrsol << '\n';
    for (i =  1; i  <= min(nrsol , 1000) ; i ++)
    g << sol[i] << ' ';
    return 0 ;
}