Cod sursa(job #1326596)

Utilizator c0rn1Goran Cornel c0rn1 Data 25 ianuarie 2015 18:11:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LMAX 2000005

using namespace std;

char n[LMAX], m[LMAX];
int N, M, pi[LMAX], sol[1005];

void KMP()
{
   int k = 0;
   for (int i=2; i<=N; i++){
      while (k>0 && n[k+1] != n[i])
         k = pi[k];
      if (n[k+1] == n[i])
         k++;
      pi[i] = k;
   }

   k = 0;
   for (int i=1; i<=M; i++){
      while (k>0 && n[k+1]!=m[i])
         k = pi[k];
      if (n[k+1] == m[i])
         k++;
      if (k == N){
         ++sol[0];
         if (sol[0]<=1000)
            sol[sol[0]] = i-N;
      }
   }
}

int main()
{
   freopen("strmatch.in", "r", stdin);
   freopen("strmatch.out", "w", stdout);
   scanf("%s\n%s", n+1, m+1);
   N = strlen(n+1);
   M = strlen(m+1);
   KMP();
   printf("%d\n", sol[0]);
   for (int i=1; i<=min(sol[0], 1000); i++)
      printf("%d ", sol[i]);

   return 0;
}