Cod sursa(job #1804551)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 12 noiembrie 2016 18:48:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>

const int NMAX = 2000000;
using namespace std;

ifstream cin ( "strmatch.in" );
ofstream cout ( "strmatch.out" );

char s[2*NMAX+5];
int pi[2*NMAX+5], sol[NMAX+5];

void kmp ( char* s, int *pi, int n ) {
  int poz = 0;
  for ( int i = 2; i <= n; i ++ ) {
    while ( s[poz + 1] != s[i] && poz > 0 )
      poz = pi[poz];
    if ( s[i] == s[poz + 1] )
      ++poz;
    pi[i] = poz;
 }
}

int main() {
  cin >> s + 1;
  int n = strlen ( s + 1 );
  s[n + 1] = '*';
  cin >> s + n + 2;
  int m = strlen ( s + 1 );
  kmp ( s, pi, m );
  int count = 0;
  for ( int i = n + 2 ; i <= m ; ++ i )
    if ( pi[i] == n )
      ++count;
  cout << count << "\n";
  for ( int i = n + 2 ; i <= m ; ++ i )
    if ( pi[i] == n )
      cout << i - 2 * n - 1 << ' ';
  cout << '\n';
  return 0;
}