Cod sursa(job #1891354)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 23 februarie 2017 22:27:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;
const int MAX_N = 2000000;
const int MAX_M = 2000000;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char s[1 + MAX_N + 1 + MAX_M + 1];
vector <int> sol;
char ceva[1 + MAX_N + 1 + MAX_M + 1];
int fail[1 + MAX_N + 1 + MAX_M];
char q[1+MAX_N];
void kmp() {
    int cnt=0;
  fscanf(fin,"%s", ceva);
    int sizeA = 0;
    for(int i=1;ceva[i-1]!=0;i++)
    {
        sizeA++;
        s[i]=ceva[i-1];
    }
    s[sizeA+1]='$';
    fscanf(fin, "%s", q);
    for(int i=sizeA+2;q[i-sizeA-2]!=0;i++)
    {
        s[i]=q[i-sizeA-2];
    }
  fail[1] = 0;
  for(int i = 2; s[i] != 0; i++) {
    int j = fail[i - 1] ;
    while (j > 0 && s[i] != s[j+1]) {
      j = fail[j];
    }
    if (s[i] == s[j+1]) {
      fail[i] = j+1;
    } else {
      fail[i] = 0;
    }
    if (fail[i] == sizeA) {
            cnt++;
            if(cnt<=1000)
            {
      sol.push_back( i - 2 * sizeA -1 );
            }
    }
  }
  fprintf(fout,"%d\n", cnt);
  for(auto circul:sol)
  {
      fprintf(fout, "%d ", circul);
  }
}
int main()
{
    kmp();
    return 0;
}