Cod sursa(job #1805825)

Utilizator tudorcomanTudor Coman tudorcoman Data 14 noiembrie 2016 14:46:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;


const int maxLen = 2000000;
char A[maxLen + 1 + maxLen + 1];
int pref[maxLen + 1 + maxLen + 1];
vector<int> pos;


void kmp_pref(char* w, int* pref) {
  int l = strlen(w);
  pref[0] = 0;
  for(int i = 1; i < l; ++ i) {
    int x = pref[i - 1];
    while(x > 0 and w[i] != w[x])
      x = pref[x - 1];
    if(w[i] == w[x])
      pref[i] = x + 1;
    else
      pref[i] = 0;
  }

}


int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  gets(A);
  int l = strlen(A);
  A[l] = '*';
  gets(A + l + 1);


  kmp_pref(A, pref);
  for(int i = 0; A[i] != '\0'; ++ i)
    if(pref[i] == l)
      pos.push_back(i - l - l);

  unsigned k = pos.size();
  printf("%u\n", k);
  if(k > 1000)
    k = 1000;
  for(int i = 0; i < k; ++ i)
    printf("%d ", pos[i]);
  printf("\n");
  return 0;
}