Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<char *> W; // vetor de enderecos das palavras
- vector<int> P; // vetor de permutacao dos indices de W
- int k = 2; // ordem da cadeia de markov
- /*
- * Compara as k primeiras palavras dos textos
- * começando em p e q */
- int wordncmp(char *p, char *q){
- int n = k;
- for(; *p == *q; p++, q++)
- if (*p == 0 && --n == 0)
- return 0;
- return *p - *q;
- }
- /*
- * Função para ordenar os indices de W
- */
- bool wordnless(int a, int b){
- return wordncmp(W[a], W[b]) < 0;
- }
- /*
- * Constroi o array de sufixos que trabalha no nivel
- * de palavras.
- */
- void build_suffix_array(char *buffer){
- /* Salva o endereco em buffer onde se inicia cada
- palavra */
- W.assign(1, buffer);
- while (scanf("%s", W.back()) != EOF){
- W.push_back(W.back() + strlen(W.back()) + 1);
- }
- /* Gera indices correspondendo a um vetor ordenado
- comparando as k primeiras palavras */
- P.resize(W.size());
- for(int i = 0; i < (int) P.size(); i++)
- P[i] = i;
- sort(P.begin(), P.end(), wordnless);
- }
- /*
- * Busca binaria para encontrar a primeira ocorrencia
- * da palavra W[curr_index] no vetor ordenado de
- * palavras
- */
- int binsearch(int curr_index){
- int l = -1, u = (int)P.size(), m;
- while (l + 1 != u){
- m = (l + u) / 2;
- if (wordnless(P[m], curr_index))
- l = m;
- else u = m;
- }
- return u;
- }
- /*
- * Gerador de texto aleatorio
- */
- void generator(){
- char buffer[100000];
- /* Lê a entrada em 'buffer' e gera o array de
- sufixos */
- build_suffix_array(buffer);
- int curr = rand() % W.size();
- for(int wleft = 100; wleft > 0; wleft--){
- /* Encontra a primeira ocorrencia, no vetor
- ordenado, da palavra word[curr] */
- int j = binsearch(curr);
- /* Para todos os trechos no texto que têm as k
- primeiras palavras iguais ao trecho corrente,
- escolha uma aleatoriamente */
- int tmp_index;
- for(int i = 0; j + i < W.size() &&
- wordncmp(W[curr], W[P[j + i]]) == 0; i++)
- if (rand() % (i+1) == 0)
- tmp_index = P[j + i];
- curr = tmp_index + 1;
- if (curr + k - 1 >= (int) W.size()) break;
- printf("%s ", W[curr + k - 1]);
- }
- printf("\n");
- }
- int main (){
- srand(time(NULL));
- generator();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement