Cod sursa(job #681325)

Utilizator dandroidDan Octavian dandroid Data 16 februarie 2012 21:44:45
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "strmatch.in"
#define OUT "strmatch.out"

//#define ONLINE_JUDGE

const int size = 2000001;
char A[size];
char B[size];

int Asize;
int occurences;
list<int> starts;

int prefixTable[size];

void buildPrefixTable()
{
  int i = 1; 
  int pi = 0;
  while (A[i] != '\0')
  {
    while (pi > 0 && A[i] != A[pi])
    {
      pi = prefixTable[pi];
    }
    if (A[i] == A[pi])
    {
      pi++;
      prefixTable[i] = pi;
    }
    i++;
  }
  Asize = i;
}

void printPrefixTable()
{
  for (int i = 0; i < Asize; i++)
  {
    cerr << prefixTable[i] << " " ;
  }
  cerr << endl;
}

void match()
{
  int i = 0;
  int m = 0;
  while (B[i] != '\0')
  {
    while (m > 0 && A[m] != B[i])
    {
      m = prefixTable[m];
    }
    if (B[i] == A[m])
    {
      m++;

      if (m == Asize)
      {
        starts.push_back(i - Asize + 1);
        occurences++;
        m = prefixTable[m - 1];
      }
    }
    i++;
  }
}

void solve(int test) {
  cin.getline(A, size); 
  cin.getline(B, size);
  buildPrefixTable();
  printPrefixTable();
//  cerr << "A " << A << endl;
//  cerr << "B " << B << endl;

  match();
  cout << occurences << endl;
  list<int>::iterator it;
  for (it = starts.begin(); it != starts.end(); it++)
  {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
#endif
   solve(1);
  return 0;
}