Cod sursa(job #219838)

Utilizator recviemAlexandru Pana recviem Data 8 noiembrie 2008 13:28:50
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <string>
#include <queue>
#define nmax 2000010
using namespace std;

string w,s;
int T[nmax],numb=0,step=1;
queue<int> sol;

void readuire()
{
  char c;
  freopen("strmatch.in","r",stdin);
  c = getc(stdin);
  while (c!='\n'){
    w += c;
    c = getc(stdin);
  }

  c = getc(stdin);
  while (c!='\n'){
    s += c;
    c = getc(stdin);
  }  
  fclose(stdin);
}

void compute_table(string w, int T[nmax])
{
  // Compute the Skip Table
  int pos = 2,cnd = 0,l=w.length();
  T[0] = -1;
  T[1] = 0;
  while (pos<l){
    // case 1 : the substring continues
    if (w[pos-1] == w[cnd]){
      T[pos] = cnd + 1;
      pos++;
      cnd++;
    }

    else
      // case 2 : Substring doesn't continue, but we might have a
      // smaller prefix
      if (cnd > 0)
	cnd = T[cnd];

      else{
	// case 3 : hopeless case ..
	T[pos] = 0;
	pos ++;
      }
  }
  step = 1;
}

void KMP(string s, string w)
{
  int pos = 0, ls = s.length(), lw = w.length();
  int cur = 0;
  while (pos+cur < ls){
    if (w[cur] == s[cur+pos]){
      cur ++;
      if (cur == lw){
	if (numb < 1000)
	  sol.push(pos);
	cur = 0;
	pos += step;
	numb++;
      }
    }
    else{
      pos += cur - T[cur];
      cur = cur > 0 ?T[cur] : 0;
    }
  }
}

void scriere()
{
  freopen("strmatch.out","w",stdout);
  printf("%d\n",numb);
  while ( !sol.empty()){
    printf("%d ",sol.front());
    sol.pop();
  }
  fclose(stdout);
}

int main()
{
  readuire();
  compute_table(w,T);
  KMP(s,w);
  scriere();
  return 0;
}