Cod sursa(job #219779)

Utilizator recviemAlexandru Pana recviem Data 8 noiembrie 2008 11:24:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <string>
#include <queue>
#define nmax 2000001
using namespace std;

string w,s;
int T[nmax];
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 (!feof(stdin)){
    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] = T[pos-1] + 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 ++;
      }
  }
}

int KMP(string s, string w)
{
  int pos = 0, ls = s.length(), lw = w.length(), numb = 0;
  int cur = 0;
  while (pos < ls-lw+1 && numb < 1000){

    while (w[cur] == s[pos+cur] && cur < lw)
      cur ++;

    if (cur == lw){
      sol.push(pos);
      cur = 0;
      pos += 1;
      numb++;
    }
    
    else{
      pos += cur - T[cur];
      cur = cur > 0 ?T[cur] : 0;
    }
  }
  return numb;
}

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

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