Cod sursa(job #1802376)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 10 noiembrie 2016 10:56:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <cstring>
using namespace std;
int NMAX = 2000000;
char s1[2000005], s2[2000005], s[4000005];
int p[4000005];
void prefix(int n){
  int x = 0, i;
  for (i = 2; i <= n; i ++){
    while (x > 0 && s[x + 1] != s[i])
      x = p[x];
    if (s[x + 1] == s[i])
      x ++;
    p[i] = x;
  }
}
int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int n, m, i, k = 0;
    gets(s1 + 1);
    m = strlen(s1 + 1);
    gets(s2 + 1);
    n = strlen(s2 + 1);
    for (i = 1; i <= m; i ++)
      s[++k] = s1[i];
    s[++k] = '#';
    for (i = 1; i <= n; i ++)
      s[++k] = s2[i];
    prefix(k);
    k = 0;
    for (i = m + 2; i <= n + m + 1; i ++)
      if (p[i] == m)
        k ++;
    printf("%d\n", k);
    k = 0;
    for (i = m + 2; i <= n + m + 1 && k <= 1000; i ++)
      if (p[i] == m){
        printf("%d ", i - 2 * m - 1);
        k ++;
      }
    return 0;
}