Cod sursa(job #1804502)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 12 noiembrie 2016 17:29:09
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[4000005];
int pi[4000005], sol[2000005];
void prefix(char* w, int *v, int n){
  int x = 0;
  for (int i = 2; i < n; i ++){
    while (w[x + 1] != w[i] && x != 0)
      x = v[x];
    if (w[i] == w[x + 1])
      x ++;
    v[i] = x;
  }
}
int main(){
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  s[n + 1] = '*';
  scanf("%s", s + n + 2);
  int m = strlen(s + 1);
  prefix(s, pi, m);
  int count = 0;
  for (int i = n + 2; i < m; i ++)
    if (pi[i] == n)
      sol[++count] = i - 2 * n - 1;
  printf("%d\n", count);
  for (int i = 1; i <= min(1000, count); i ++)
    printf("%d ", sol[i]);
  return 0;
}