Advertisement
Guest User

Untitled

a guest
Apr 25th, 2011
400
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<char *> W; // vetor de enderecos das palavras
  8. vector<int> P; // vetor de permutacao dos indices de W
  9. int k = 2; // ordem da cadeia de markov
  10.  
  11. /*
  12.  * Compara as k primeiras palavras dos textos
  13.  * começando em p e q */
  14. int wordncmp(char *p, char *q){
  15.   int n = k;
  16.   for(; *p == *q; p++, q++)
  17.     if (*p == 0 && --n == 0)
  18.       return 0;
  19.   return *p - *q;
  20. }
  21. /*
  22.  * Função para ordenar os indices de W
  23.  */
  24. bool wordnless(int a, int b){
  25.   return wordncmp(W[a], W[b]) < 0;
  26. }
  27. /*
  28.  * Constroi o array de sufixos que trabalha no nivel
  29.  * de palavras.
  30.  */
  31. void build_suffix_array(char *buffer){
  32.   /* Salva o endereco em buffer onde se inicia cada
  33.      palavra */
  34.   W.assign(1, buffer);
  35.   while (scanf("%s", W.back()) != EOF){
  36.     W.push_back(W.back() + strlen(W.back()) + 1);
  37.   }
  38.   /* Gera indices correspondendo a um vetor ordenado
  39.      comparando as k primeiras palavras */
  40.   P.resize(W.size());
  41.   for(int i = 0; i < (int) P.size(); i++)
  42.     P[i] = i;
  43.   sort(P.begin(), P.end(), wordnless);
  44. }
  45. /*
  46.  * Busca binaria para encontrar a primeira ocorrencia
  47.  * da palavra W[curr_index] no vetor ordenado de
  48.  * palavras
  49.  */
  50. int binsearch(int curr_index){
  51.   int l = -1, u = (int)P.size(), m;
  52.   while (l + 1 != u){
  53.     m = (l + u) / 2;
  54.     if (wordnless(P[m], curr_index))
  55.       l = m;
  56.     else u = m;
  57.   }
  58.   return u;
  59. }
  60. /*
  61.  * Gerador de texto aleatorio
  62.  */
  63. void generator(){
  64.  
  65.   char buffer[100000];
  66.   /* Lê a entrada em 'buffer' e gera o array de
  67.      sufixos */
  68.   build_suffix_array(buffer);
  69.  
  70.   int curr = rand() % W.size();
  71.   for(int wleft = 100; wleft > 0; wleft--){
  72.  
  73.     /* Encontra a primeira ocorrencia, no vetor
  74.        ordenado, da palavra word[curr] */
  75.     int j = binsearch(curr);
  76.  
  77.     /* Para todos os trechos no texto que têm as k
  78.        primeiras palavras iguais ao trecho corrente,
  79.        escolha uma aleatoriamente */
  80.     int tmp_index;
  81.     for(int i = 0; j + i < W.size() &&
  82.       wordncmp(W[curr], W[P[j + i]]) == 0; i++)
  83.       if (rand() % (i+1) == 0)
  84.     tmp_index = P[j + i];
  85.     curr = tmp_index + 1;
  86.     if (curr + k - 1 >= (int) W.size()) break;
  87.     printf("%s ", W[curr + k - 1]);
  88.   }
  89.   printf("\n");
  90. }
  91.  
  92. int main (){
  93.   srand(time(NULL));
  94.   generator();
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement