C Converter para linguagem C

[arfneto]

 

Sem stress algum. Imagino que você tenha digitado meu nome por engano lá então. Porque o do autor do tópico lá não está  

 

 

Ainda não estamos do mesmo lado dessa questão.  Eu já escrevi ao menos 3 desses "recuperadores" de arquivo e aí esse enunciado me chamou mais atenção. E eu já tinha dito que o enunciado era "bobinho".E aí tentei até dar sentido ao texto, até ler "sequências a verificar" de 1 byte"  e o lance do mississipi. O texto ruim sem conexão com a realidade e só pra parecer sofisticado me atingiu afinal.
 

Aí eu parei. Mas logo em seguida vi sua mensagem e aí fui ver como você tinha visto sentido naquilo. E o resto já se sabe.

 

Mas afinal porque a gente não concorda com o lance do mississippi?
 

 

Note os parenteses vermelhos e azuis em torno da expressão. Essa é a lógica. 



E entenda que esta sequência não está duplicada na palavra. Não há lógica que faça isso acontecer. Você tinha errado ontem e errou hoje nesse caso. Não são 9 mas apenas 8 strings duplicadas.

 

Estamos do mesmo lado agora? Entende que aquilo está errado? Essa é a lógica. Um programa correto não vai mostrar 9... 

 

Esse é o autor.

 

adicionado 6 minutos depois

1 hora atrás, Simon Viegas disse:

A árvore que eu postei é Trie (pelo menos é isso que diz o site online que eu criei a árvore

 

Sim. É. Entendeu que se usar o programa que eu mostrei ele gera o #include para você por no programa, passando a letra lida na entrada direto para a posição certa na tabela? 

 

1 hora atrás, Simon Viegas disse:

A parte do teu código confesso que fiquei longe de entender ainda...(não sou um grande programador, e conheço ainda menos C). Eu tinha em mente antes chegarmos a um senso comum de qual é o entendimento correto do problema, para só depois, caso necessário, tirar algumas dúvidas com vocês

 

Entendo.

 

Você entendeu a tabela abaixo? 

const char ref[256] =
{

  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   1,   0,   2,   0,
  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,   0,   0,   0,   0,   0,   0,
  0,  13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,
 28,  29,  30,  31,  32,  33,  34,  35,  36,  37,  38,   0,   0,   0,   0,   0,
  0,  39,  40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  50,  51,  52,  53,
 54,  55,  56,  57,  58,  59,  60,  61,  62,  63,  64,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0

}; // ARFNeto '20

é a saída daquele programa C, você roda com o nome do .h como argumento e ele gera o arquivo para você incluir

Como no exemplo

#include "stdio.h"
#include "trecho.h"
int main()
{
	int l = 0;
	printf("\n");
	for (int i = 0; i < 256; i += 1)
		if (idx[i] != 0) // tem representacao
		{	printf("  %2d:%3d %c", idx[i], i, i);
			if (l % 8 == 7) printf("\n");
			l += 1;
		};	// if()
	printf("\n");
};

Que vai mapear o conteúdo da entrada automaticamente para o universo de 64 bytes do enunciado:

   1: 44 ,   2: 46 .   3: 48 0   4: 49 1   5: 50 2   6: 51 3   7: 52 4   8: 53 5
   9: 54 6  10: 55 7  11: 56 8  12: 57 9  13: 65 A  14: 66 B  15: 67 C  16: 68 D
  17: 69 E  18: 70 F  19: 71 G  20: 72 H  21: 73 I  22: 74 J  23: 75 K  24: 76 L
  25: 77 M  26: 78 N  27: 79 O  28: 80 P  29: 81 Q  30: 82 R  31: 83 S  32: 84 T
  33: 85 U  34: 86 V  35: 87 W  36: 88 X  37: 89 Y  38: 90 Z  39: 97 a  40: 98 b
  41: 99 c  42:100 d  43:101 e  44:102 f  45:103 g  46:104 h  47:105 i  48:106 j
  49:107 k  50:108 l  51:109 m  52:110 n  53:111 o  54:112 p  55:113 q  56:114 r
  57:115 s  58:116 t  59:117 u  60:118 v  61:119 w  62:120 x  63:121 y  64:122 z

Ajudei a entender?

[Simon Viegas]

@arfneto, vamos lá:

 

16 horas atrás, arfneto disse:

você tinha errado ontem e errou hoje nesse caso

Em relação a minha lógica, apenas houve erros nas demonstrações da execução. A minha lógica não mudou.

 

Na tua lógica, qual é o número de diferentes subsequências contíguas que aparecem pelo menos duas vezes na seqüência em mississipi?

 

Ex.:

ENTRADA
nusssissippi 

SAÍDA
8

Correto? Quais seriam 8 sequências?

 

Então, da forma que eu entendi seriam 9 sequências. Essas: [i, is, iss, issi, p, s, ss, si, ssi]. Cada uma delas ocorrem pelo menos 2 vezes. Foi assim que eu entendi, e está, por coincidência ou não, correspondendo.

 

Aqui uma demonstração:

 

20 horas atrás, Simon Viegas disse:

 

Existem 13 repetições de sequências de bytes... mas o enunciado quer apenas as repetições únicas... logo, dá 9.

 

Achei esse site (https://www.udebug.com/URI/1377) que testa as entradas... todos os resultados batem.

 

Ex.:

 

Outros testes:

 

Aqui continua batendo igual...

 

Então, estou tendo dificuldade para implementar um código em C (não na lógica, mas sim pela sintaxe do C. Eu sei o que é para fazer, só não sei como, rs).

 

Fazendo um testes individuais está batendo certinho... mas como não tenho as manhas, não consegui colocar um vetor com os dados de entrada... ou seja: não está funcionando bem para várias entradas. Mas isso não tem qualquer relação com a lógica...

 

Segue o código com tentativa de colocar várias entradas:

#include "stdio.h"
#include "string.h"

int main()
{

    
    //scanf("%s", entrada);
    char ENTRADAS[256][256] = {",BQgnwsjrHMK1raD7Xjd,9Ik9rcwsGGwhPttlN3jaju15H6VdGV6IcnACgLL8HODqZi906Assg,mQTdvp,fHY8yhJfQpvrJmIHqSp2bnqbVspBJ3P2sH5un6A2z7NyzkfB1hKd1HbIUVWuH8yTGI,WYAic5s5Esacj937j.3UsdkvbgmLm1ll5rq1pu7ukwwGtXJDVJ3D31lhiArw7AeLyWdPgWF,gSZOIz0rFUiy6nCntLW1Jx2vZxCTqwMc6",
                               "*"};
    int e=0;
    do {
        char entrada[256], subString1[200]="", subString2[200]="", listaRepetidos[256][256];
        int cont=0, pos1, pos2, qtd, contRepetidos = 0;
        strcpy(entrada, ENTRADAS[e]);
        int tamanho = strlen(entrada);
        
        for (int qtd=1; qtd < tamanho; qtd++) {
            for (int pos1=0; pos1 < tamanho-1; pos1++) {
                bool repete = false;
                memcpy(subString1, &entrada[pos1], qtd);     
                for (int pos2=pos1+1; pos2 < tamanho; pos2++) {
                    memcpy(subString2, &entrada[pos2], qtd);
                    if (strcmp(subString1, subString2) == 0) {
                        cont++;
                        repete = true;
                        bool novo = true;
                        for (int r=0; r<=contRepetidos; r++) {
                            if (strcmp(listaRepetidos[r], subString1) == 0) {
                                novo=false;
                            }
                        }
                        if (novo) {
                            for(int x=0; x<strlen(subString1); x++) {
                                listaRepetidos[contRepetidos][x] = subString1[x];            
                            }                                
                            contRepetidos++;   
                        }
                    }
                    if (repete) break;
                }
            }
        }


        printf("\nENTRADA: %s\nSAIDA: %d", entrada, contRepetidos );
        e++;
    } while (strcmp(ENTRADAS[e], "*") != 0);
    
    return 0;
}; // main()

 

Calcula certinho... só não consegue calcular mais de um em uma única execução... você poderia dar uma ajustada nesse código? 

 

[arfneto]

 

Acho que não entendeu o lance dos parenteses em azul e vermelho quando eu postei ontem.

 

Você já postou várias sequências distintas tentando acertar o número 9 do enunciado

 

Mas vamos ver em relação às últimas:

 

• "issi" não está duplicado em "mississippi" veja a figura que mostrei. A primeira ocorrência está na posição 1 da string e você quer aceitar uma duplicata que começa na posição 4, aproveitando o último "i" de uma sequência para começar a próxima. Elas não podem estar "encavaladas" digamos. Uma de 1-4 e outra de 4-7. Não é uma repetição. Ela só poderia aparecer por exemplo em MISSIISSIPPI, inserindo outro i na posição 5. Como é o caso do exemplo

  "say.twice,say.twice"

  do enunciado. Sobre as anteriores, "pp" não está repetida, "is" você havia listado duas vezes.
   
• Sequências de 1 byte descritas como

  Citação

  quantas sequências precisam de verificação, isto é o número de sequências diferentes de bytes contíguos que aparecem em pelo menos duas vezes nos dados.

  
  é algo folclórico. São sequências de UM byte. Como verificar sequências de UM byte? E se o byte existe vai ter um conteúdo. Se são 64 letras de possíveis 256 combinações você pode considerar 25% de "verificações" à toa.
  Se você aceitar que sequências de 1 byte tem sentido para se considerar uma repetição serão mesmo 8 repetições em mississippi. Não 9.
  
  O seu programa
  
  Vou ver a seguir se entendo seu programa. Essa tabela de 64k bytes era para listar as possíveis combinações? Poderia explicar um pouco sua ideia? 
   

• Não se interessou pelo uso do trie? ficaria bem mais fácil... e o mapa (opcional) que mostrei é para uma tabela de 64 posições, 1024 vezes menos que sua tabela de 65536 bytes
  
  mais a noite vou ver seu programa sim. 
  
  Em relação ao site https://www.udebug.com/URI/1377 nada muda sobre esse programa. Não testei de fato para as outras strings porque tinha abandonado o programa. Isso porque achei muito bobinho e o autor do tópico também acho que se foi há muito. Por outro lado, pode ser que o site entenda as respostas corretas, considerando a interpretação discutível das sequências de um byte e o enunciado como um todo.
  
  Vinha escrevendo isso para deixar um exemplo de certas técnicas que aparecem muito na prática, e vou até concluir para acrescentar uma implementação do trie em C com comentários em português  nos próximos dias de confinamento  conforme eu tenha oportunidade 

[arfneto]

1 hora atrás, arfneto disse:

Vou ver a seguir se entendo seu programa. Essa tabela de 64k bytes era para listar as possíveis combinações? Poderia explicar um pouco sua ideia? 

 

Não que eu tenha entendido, mas ao menos li seu programa. A tabela era apenas para simular a entrada? O que tem dentro?

[Simon Viegas]

@arfneto, sim... apenas foi uma tentativa frustada de inserir as entradas automaticamente... era apenas para demostrar os resultados de uma vez só. Entrando um a um funciona (aquilo que propus a fazer, não necessariamente o que é necessário de fato para o enunciado. Todos os valores batem igual... pode ser coincidência).

 

adicionado 0 minutos depois

Já comecei me batendo para fazer um "vetor de strings", rs.

[arfneto]

Estamos afinal de acordo de issi não é duplicada em mississippi?

 

2 minutos atrás, Simon Viegas disse:

Já comecei me batendo para fazer um "vetor de strings", rs

 

Use a técnica do sistema. Não tem como dar errado ou a gente já teria visto...

 

    int main(int argc, char** argc);

ou 

    public static void main(String[] args)

em java  

 

São sempre vetores de strings.

 

Vou te mostrar uma maneira de construir. Acho que tenho um exemplo que escrevi para alguém... 

 

Para esse programa, sem criar de fato o vetor como em C ou C++ ou java:
 

#include <string.h>
#include <stdio.h>
int main(int argc, char** argv)
{
	const char exemplo[7][50] =
	{
		"ababcabb",
		"mississippi",
		"aaaaaaaaaaaaaaaaaaaaaaaaaa",
		"012345678,abcdefg.STUVWXYZ",
		"say.twice,say.twice",
		"say.twice,sa,sa.twice",
		"*"
	};
	const char* final = "*"; // marca de final
	int i = 0, n = 0;
	while (strcmp(exemplo[i], final) != 0)
	{	// ate ler "*"
		printf("%5d [%4d]   '%s'\n", 1 + i, strlen(exemplo[i]), exemplo[i]);
		i = i + 1; // ve o proximo
	};	// while
	return 0;
};	// main()

Mostra

    1 [   8]   'ababcabb'
    2 [  11]   'mississippi'
    3 [  26]   'aaaaaaaaaaaaaaaaaaaaaaaaaa'
    4 [  26]   '012345678,abcdefg.STUVWXYZ'
    5 [  19]   'say.twice,say.twice'
    6 [  21]   'say.twice,sa,sa.twice'

Depois te mostro como construir um vetor 

 

adicionado 5 minutos depois

Note que assim também funciona:

#include <string.h>
#include <stdio.h>
int main(int argc, char** argv)
{
	const char exemplo[7][50] =
	{	[4] = "mississippi",
		[1] = "say.twice,say.twice",
	};
	printf("%5d [%4d]   '%s'\n", 1, strlen(exemplo[1]), exemplo[1]);
	printf("%5d [%4d]   '%s'\n", 4, strlen(exemplo[4]), exemplo[4]);
	return 0;
};	// main()

Declarando só alguns dos valores, e mesmo fora de ordem

    1 [  19]   'say.twice,say.twice'
    4 [  11]   'mississippi'

 

[Simon Viegas]

50 minutos atrás, arfneto disse:

Estamos afinal de acordo de issi não é duplicada em mississippi?

 

OK. Não é "duplicada". Talvez um termo melhor seria "repetidas"?... Se não servir também - apesar de ser importante utilizar um termo mais correto e preciso - vamos chamar o que eu procuro de "copeliscos". Daí, existem 13 "copeliscos" em "mississipi". O "issi" é um deles".

 

Citação

mississipi

mississipi

 

É isso que eu estou contando.

 

Veja:

 

Eu estou entendendo que o enunciado queria apenas a quantidade "copeliscos" distintos entre si... perceba que no trecho rasurado tem "is", logo foi um erro foi na execução do algoritmo!!! ele já foi citado no 4... não faria sentido! Apenas errei ao fazer de cabeça na hora... Todos os 9 citados são "copelistos" e são distintos entre si.

 

 

Segue um resultado de um novo teste:

Peguei uma string de 1315 caracteres no site e executei lá:

7SygxhcDARmBjE4lzmoOOXSLR5EWNMU4LZ.TG3thal0jmV0hBQmMlXTJ2ktwIXE447EK45SAQFbjyMbo6Uy4YOio5ZbtzfZiEnGZhw1FaVAKvjiOGGBMdEOUD8qT2QvV9XTI1xvDRcOHRHWEZi85OAZmiSNUGNT1,UT6Qb1CrItic2I3DTK4iMrVJmVE,gJJkohcoF8LCvcHcqf7ez6RkiRFxKpd6nEaixJcj4t,YKD1u2cZssNAyjPLk8WN7fhuGsRdetHY9xnlEXbMUHtozWYiMC6rP1fO6hfmL5phJ16RjkPCaoLo1hVqsmukSNbd..zMwYffoilE.gJDWGgJuuhg1tMzSHJTu.qx9gQ0LwPRKWwYMHDuEHJX56zgrSsUKrrPe9NDqO8AIpRIkxtP70Qzfjvzdq2pw9fJsEJh2gR0IQj2elpQuvfgbibBRv4xsluooYh6b3Ealkz08f6GpoCbv.gtVdapadLXIb6.yf.gf3cMBn7svMwrP1lj4H19jSHu1tLCJ2Zo35TuhQ7ipKC,LZ5gV4aRtpVaVWVBltKHlycfPLIlJrvsXb4r6qiHh1474Gbe2K6gOBObQgxI71Qs1NVYdX2LoKKq4QdDnXCg2miqWvdv9ychAShYWJYboLAexxCW4bZOEXj7LAnTtbg6gANyRTJ9X,cH9V1fGEN0gsuiWDEXK5DYI33SBzYFE8fUt61IRoFYx5qc4LDPxjX3xmH3OTgX9IlZ,,frdAdR5TMUN7ZEw3NsmHla5Yi61675QimAok8Mv1.wKNiwilPkO.Dp4VFdWm.h9BZd2LYRrA,bxXdCvpFNvQaSmU0tvG8LEbIwI1mdxKs4OHn1LjWY6UCGD1UYm9CC3caB5aZ1nBEc,.nRGcfY.syYuo2O9SgZVL1yLppjDgmNerSfVdgVlECRx,0.q2JYT0RxnQhiUVdVFIrm4rAXiAsrpqp7THBIB1hFzyd5NCSJ45LgK3PbDoGVKlWO91vkGX05XJSKYwVk4Eq9B7CMYbUk,2.lM86YKWyR9rQr2LZTfy55gNBPV8LSgBIVr8XIp5BaLRKjBqGsiXialbnr8hSCJadzN.JJjwM9r5dtjHFdQVMCusBMcQSI8Tktok386nHSQdU4OEyirB7vhHSWNTnh7SEKWOw2kNZuwqo,GqYNN8UXo4P4ux2sgePu0GOyHSf9.QlWA,wQtCO6qD6fYXqlh8qRb5uQNK.Wlxmt8ZSy8br31zgFNdc6LD9Yb9d0fxh0JG5XVZB6m0qXK01pDv1OiVyXBYC,HmhrWn7rCjlxQ9nVh2XC6VrCy6iU3Hi

 

Deram 219 "copeliscos" únicos*. Veja:

 

 

Fui no meu programa e executei:

 

 

Deu 219.

 

Então, só para reforçar: não estou dizendo que esse algoritmo é uma resposta válida, mas apenas demonstrando que está coerente no que eu entendi.. da mesma forma não estou dizendo que o que eu entendi está necessariamente certo, mas apenas que está correspondendo 100% com todos os testes efetuados até o momento (acho que poderia chamar de conjectura)... pode ser apenas coincidência.

 

 Modifiquei o código para ler apenas uma string, segue:

#include "stdio.h"
#include "string.h"

int main()
{
    char entrada[1400], subString1[1400]="", subString2[1400]="", listaRepetidos[256][1400];
    int cont=0, pos1, pos2, qtd, contRepetidos = 0;
    
    scanf("%s", entrada);

    int tamanho = strlen(entrada);

    for (int qtd=1; qtd < tamanho; qtd++) {
        for (int pos1=0; pos1 < tamanho-1; pos1++) {
            bool repete = false;
            memcpy(subString1, &entrada[pos1], qtd);     
            for (int pos2=pos1+1; pos2 < tamanho; pos2++) {
                memcpy(subString2, &entrada[pos2], qtd);
                if (strcmp(subString1, subString2) == 0) {
                    cont++;
                    repete = true;
                    bool novo = true;
                    for (int r=0; r<=contRepetidos; r++) {
                        if (strcmp(listaRepetidos[r], subString1) == 0) {
                            novo=false;
                        }
                    }
                    if (novo) {
                        for(int x=0; x<strlen(subString1); x++) {
                            listaRepetidos[contRepetidos][x] = subString1[x];            
                        }                                
                        contRepetidos++;   
                    }
                }
                if (repete) break;
            }
        }
    }

    printf("\nENTRADA: %s\nSAIDA: %d", entrada, contRepetidos );

    return 0;
}; // main()

 

O código anterior foi apenas uma forma que imaginei para já deixar algumas entradas no próprio código (só para testar mais de uma de uma vez... tentei fazer só por um desafio mesmo, mas falhei, rs)... Mas acho que o que importa é a lógica para uma string mesmo (pois se para uma string tiver errado, não adiantaria muita coisa para N strings)...

 

 

[Ansi C]

No exame fica pouco evidente, mas com foi dito que existia cópia dos arquivos então cada byte repetido

(Ex.: i, s, p) são dados inspecionáveis.

 

[arfneto]

não adianta: se está encavalado não é uma repetição. entenda isso.

 

ISSISSI não tem a ISSI repetida como você identificou. Não é uma repetição. Em mississippi temos 11 letras, mas pode pensar só no caso mais simples: issi repetido. Seu programa vai dizer que em uma string de 7 posições tem uma de 4 bytes REPETIDA? Sério? Na string "ISSISSI" seu programa acha uma repetição? 
Na posição 1234 tem uma string "issi" então uma possível repetição não pode começar na posição 4. Entende isso? Repetição não pode contar com a última letra da PRÓPRIA string. 

 

Seu programa diria que em ISSISSI que só tem 7 letras tem uma string repetida de 4 letras? É isso que está tentando me dizer desde ontem...

 

EM ISSIISSI sim...

 

issi só pode se repetir a partir de 5. Integralmente. Não pode "emprestar" uma letra

 

Aqui sim:

 

adicionado 20 minutos depois

36 minutos atrás, Simon Viegas disse:

O código anterior foi apenas uma forma que imaginei para já deixar algumas entradas no próprio código (só para testar mais de uma de uma vez... tentei fazer só por um desafio mesmo, mas falhei, rs)... Mas acho que o que importa é a lógica para uma string mesmo (pois se para uma string tiver errado, não adiantaria muita coisa para N strings)..

 

Algo assim serviria, como te mostrei:

	const char exemplo[6][50] =
	{	"ababcabb",
		"mississippi",
		"aaaaaaaaaaaaaaaaaaaaaaaaaa",
		"012345678,abcdefg.STUVWXYZ",
		"say.twice,sa,sa.twice",
		"*"
	};
    const char* final = "*"; // marca de final

    int i = 1;
    while (strcmp(exemplo[i], final) != 0)
    {	// ate ler "*"
        printf("%5d   %s\n", i, exemplo[i]);
        lista_dups(exemplo[i]);
        i += 1;
    }

Tem razão, basta uma ou outra string com casos particulares. Mas não vai ler 9 sub sequências naquele exemplo e se a correção espera 9 não adianta. Vou escrever um pra ver  se o site diz que está errado  

 

Seu novo programa passou de um vetor de 64K para mais de 300K de alocação estática. Meu compilador rejeitou  vou ter que mudar algo para testar

[Ansi C]

Pode ser um caso especial de sequências adjacentes.

Nesse caso o i 

 

Exemplo:

Sim a Adjacência: missississ

Não a Adjacência: mississiiss

 

 

[Simon Viegas]

Qual a saída desejada?

 

Vide:

 

O que é uma "subsequência contígua"? Vejam:

 

 

 

Ou seja, apesar dos erros de português, o enunciado está dizendo algo como apenas as "subsequências contíguas" "a", "b" e "ab" são repetidas para "ababcabb". Então, vamos considerar que não sabemos o que é "subsequências contíguas" ou "subsequências repetidos contíguas"... mas ele diz que isso, sei lá o que seja, só são "a", "b" e "ab". E é isso que estou me baseando.

 

Agora reparem: 

"ababcabb"

"ababcabb"

 

"ababcabb"

"ababcabb"

 

"ababcabb"

"ababcabb"

 

Para qualquer outra subsequências contíguas isso não ocorre...

 

Para "mississippi" existem 9 subsequências contíguas diferentes.... o que inclui o "issi". Veja:

"mississippi"

"mississippi"

 

Seguem todas as "subsequências contíguas" que se repetem:
 

 

Se quiser podem testar aí...cada uma das subsequências contíguas que estão entre " podem ser localizadas pelo menos de duas formas diferentes em mississippi. (não importa parte de uma está eventualmente "encavalado" com outra -... pois é isso que ele quer para o meu entendimento)

 

 

 

 

@arfneto, de um modo geral, o que eu quero dizer é que para analisar um problema, não necessariamente importaria se ele faz algum sentido ou não.. o cerne está no que ele quer. "A quantidade de ocorrência de alguma coisa". Veja que também não me importa para que esse dado será utilizado... estou apenas no escopo da função... que é receber uma string e retornar um inteiro.

 

 

 

ADENDO:

Veja o conteúdo da versão em inglês:

 

 

Traduzindo pelo Google Translator:

 

 

Perceba que traduzindo direto do inglês faz mais sentido!!! E se encaixa perfeitamente no que deduzi...

[arfneto]

Está bem. 

 

Então devo concluir que você de fato acha que 4324324 uma sequência de 7 dígitos, tem uma repetição da sequência 4324 de 4 dígitos? Está bem.

Outros podem imaginar que para uma coisa se repetir você precisa de um igual comprimento. Uma cópia. Uma repetição. Não adianta traduzir o enunciado. Uma repetição que conta com parte do original? Você olha no resto para ver se ela está repetida. Essa é a noção de repetição. 4324 só poderia se repetir a partir da posição 4.

 

Ou não  

[arfneto]

 

2 horas atrás, Simon Viegas disse:

Traduzindo pelo Google Translator

 

Entenda que URI é uma abreviatura de Universidade Regional Integrada, uma escola de Erechim - RS no nosso próprio Brasil. Traduzir do inglês pode bem ser o caso de traduzir de volta algo que foi inicialmente escrito em português do Brasil. Essa plataforma foi projetada por professores e alunos de lá. Que falam português com um sotaque diferente e expressões diferentes do que se usa na minha cidade por exemplo, mas ainda português

 

E esse caso aqui não depende de tradução. Você pode até considerar --- como uma interpretação livre --- se uma sub-string está repetida numa string maior considerando também partes da própria string que está buscando. Afinal é a tal liberdade.

 

Mas entenda que em geral isso não faz sentido. E aqui não faz sentido

 

Veja o bloco de notas do Windows, o Write, o Word, o vi no linux, o grep, o awk, o sed. Eles não vão achar duas vezes a string issi em ississi ou mississippi. Vão achar uma só.

 

Pense nesse comando por exemplo, do vi no Unix/Linux: 

:1,$s/issi/valor/c

Isso diz para o editor substituir todas as ocorrências de "issi" por "valor" no texto inteiro. Mas pedindo confirmação. Esse é o objetivo do 'c' final. Se você estiver editando esse arquivo:
 

 

ele não via achar a sequência repetida que você diz que existe. Vai achar as duas na linha dois e a primeira na linha 1. E nenhum editor. Nem o Control-F no navegador Chrome ou no Edge. Um match Tem que ser uma coisa que você possa substituir. Entenda a confusão que pode dar essa sua interpretação.

Se trocar o 'c' por 'g' de global no comando ele vai trocar todos. Eis o resultado de 

:1,$s/issi/valor/g

 

 

Eu sei que você acha que são 4.

Mas esse é um editor de texto e é diferente e tal. Mas e se fosse um sistema de arquivos?
Acha mesmo que um sistema de arquivos ia usar uma cópia do arquivo a partir de um pedaço do próprio arquivo?

NUNCA.

Um sistema de arquivos aloca uma outra área para a nova versão do arquivo. E trabalha na versão nova até você salvar o arquivo. Aí libera a área anterior no disco.

Imagine se ele usar um pedaço do próprio arquivo na próxima versão e o usuário resolva sair sem salvar... Impossível, porque já corrompeu uma parte do arquivo original.

 

É assim. Não é a minha lógica. Por acaso é o problema 1377 desse serviço. E todos esses outros contextos de que falei.

 

Do próprio enunciado

 

Citação

você de repente se lembrou de que o sistema de arquivos também manteve várias cópias de cada arquivo, portanto, apenas os pedaços de bytes contíguos que se repetem tem a chance de ser um arquivo. Além disso, para cada repetição dos mesmos bytes contíguos, apenas uma cópia precisa ser verificada

 

Acha mesmo que ISSI pode estar repetida em MISSISSIPPI depois de ler isso no enunciado para escrever esse programa?  Acha que isso teria uma chance de ser uma cópia do arquivo? 

 

Não tem. Espero que tenha compreendido. Pode ser como você quer, mas quase nunca é. Parece a minha vida  

 

De volta ao seu programa

Seu programa está então correto, a menos dessa questão ideológica? funciona para várias strings? Porque usou aquelas áreas enormes de memória estática? Ainda quer que eu veja algo nele?

 

[Simon Viegas]

2 horas atrás, arfneto disse:

Então devo concluir que você de fato acha que 4324324 uma sequência de 7 dígitos, tem uma repetição da sequência 4324 de 4 dígitos? Está bem.

 

Se desapegue da definição... e sim na necessidade de algo. Não importa se isso não se chama "repetição", mas apenas que estou contando "isso"... você pode dar o nome que quiser.

 

 

Vamos testar essa string:

No meu programa:

 

 

No site:

 

Também deu certo!

 

 

Apenas como demonstração, segue a lista:

4
3
2
43
32
24
432
324
4324

 

 

 

 

[arfneto]

6 minutos atrás, Simon Viegas disse:

Se desapegue da definição... e sim na necessidade de algo. Não importa se isso não se chama "repetição", mas apenas que estou contando "isso"... você pode dar o nome que quiser

 

Pois é. Espero que faça mais sentido agora com o que te expliquei acima.

[Simon Viegas]

16 minutos atrás, arfneto disse:

Seu programa está então correto, a menos dessa questão ideológica?

Eu fiz o programa da forma que eu entendi o enunciado... e deu "certo".. as respostas sempre bateram.

 

 

16 minutos atrás, arfneto disse:

funciona para várias strings?

Funcionou com toda e qualquer string compatível que testei. O site tem alguns exemplos de imput... apenas limitei os testes com o limite dos meus arrays.

 

 

16 minutos atrás, arfneto disse:

Porque usou aquelas áreas enormes de memória estática?

Pura e simplesmente limitação técnica... ou seja: não sei/soube fazer com ponteiro ou qualquer outra estrutura melhor. Com trie também vai funcionar (mas obviamente iria ter ainda mais dificuldades).

 

 

16 minutos atrás, arfneto disse:

Ainda quer que eu veja algo nele?

Sim! a ideia seria você entender minha linha de raciocínio e otimizar a implementação do algoritmo.

 

adicionado 4 minutos depois

@arfneto, para eu tentar entender a tua forma de interpretação... se inserir mississippi, a saída seria 8? Daí, liste cada uma dessas repetições.

 

[Ansi C]

Para quem chegar agora um Resumo

 

 

Um nos diz que o algoritmo do no examinador (que com certeza é um computador) é inconsistente.

O outro diz que a suposição que se tem por verdadeira é a entrada e a saída.

~~/ /~~

 

 

"(sub)sequências contíguas"

Acho que ficou pouco evidente o significado no contexto que são Strings sem espaços Em branco.

[Simon Viegas]

44 minutos atrás, Mauro Britivaldo disse:

 

adicionado 14 minutos depois

4 horas atrás, Simon Viegas disse:

Então, vamos considerar que não sabemos o que é "subsequências contíguas" ou "subsequências repetidos contíguas"... mas ele diz que isso, sei lá o que seja, só são "a", "b" e "ab"

São (com quase 99%) Strings sem espaços embranco.

 

Como assim espaços em branco?

 

Eu não entendi o que quis dizer, mas eu estava dizendo que, pelo entendi (errado ou não), as "diferentes subsequências contíguas" de "ababcabb" seriam "a", "b" e "ab". Eu não sei o que é isso, apenas estou listando... por isso a saída deveria ser 3.

 

Assim como para "mississippi" existiriam 9 "diferentes subsequências contíguas", ou seja: ainda sem eu saber o que é isso, criei uma lógica (errada ou não). Apenas estou tentando demonstrar aquilo que eu entendi... e ainda não consegui entender o que o @arfneto entendeu (muito por minha incompetência técnica, outra parte por talvez está preso na minha interpretação errônea).

 

 

@Mauro Britivaldo, se a entrada for mississippi, qual seria o valor da quantidade de "diferentes subsequências contíguas"? Poderia listar cada uma delas? Creio que vendo um exemplo eu consiga entender melhor...

 

[Ansi C]

Ahh! Não tem segredos é só um termo usado para o tipo de entrada.

O tipo de string na entrada não deve ter espaço vazio. Ou seja, uma sequencia contigua.

 

 

O que ele(@arfneto) me diz que os arquivos estão contíguos, ou seja, sem fragmentação, sem falta.

Assim, miss(i)ssippi esse i em destaque não poderia ser o primeiro de um segundo issi porque fragmentação não faz parte dos processos do sistema.

 

Contudo, o contíguos aqui não significa isso, significa apenas que não existia espaços, era tudo junto e misturado.

[Simon Viegas]

E sobre?
 

1 hora atrás, Simon Viegas disse:

@Mauro Britivaldo, se a entrada for mississippi, qual seria o valor da quantidade de "diferentes subsequências contíguas"? Poderia listar cada uma delas? Creio que vendo um exemplo eu consiga entender melhor...

[Ansi C]

"se a entrada for mississippi"

Entendemos aqui que a polêmica é iss(i)ssi

 

Em todo caso um programa pode fazer exatamente como uma pessoa comum faria.

 

Uma busca byte a byte na largura de 1 byte.

m1, i4, s4, p2: Todo < 2 não precisa ser inspecionado fica [i, s, p].

 

Uma busca byte a byte na largura de 2 byte.

mi1, is2, ss2, si2, ip1, pi1: Todo < 2 não precisa ser inspecionado fica [is, ss, si].

 

Uma busca byte a byte na largura de 3 byte.

mis1, iss2, ssi2, sis1, sip1, ipp1, ppi1: Todo < 2 não precisa ser inspecionado fica [iss, ssi].

 

Uma busca byte a byte na largura de 4 byte.

miss1, issi2, ssis1, ssip1, sipp1, ippi1: Todo < 2 não precisa ser inspecionado fica [issi].

 

Uma busca byte a byte na largura de 5 byte.

missi1, issis1, ssiss1, sissi1, issip1, sippi1: Todo < 2 não precisa ser inspecionado fica [Vazio].

 

Uma busca byte a byte na largura de 6 byte.

[Vazio] porque uma cópia exige destino com dobro da largura.

 

Logo de todas essas sub-strings contiguas apenas as inspecionáveis no meu entendimento são ...

 

 

1. Conjunto [i, s, p]
2. Conjunto [is, ss, si]
3. Conjunto [iss, ssi]
4. Conjunto [issi]
5. Conjunto Vazio

Total: 9

 

 

 

 

[Simon Viegas]

4 horas atrás, Simon Viegas disse:

@arfneto, para eu tentar entender a tua forma de interpretação... se inserir mississippi, a saída seria 8? Daí, liste cada uma dessas repetições.

 

@arfneto, e tu? Quais seriam as "diferentes subsequências contíguas"?

 

[arfneto]

6 horas atrás, Simon Viegas disse:

Eu fiz o programa da forma que eu entendi o enunciado... e deu "certo".. as respostas sempre bateram

 

Seu programa parece certo. Exceto nesse aspecto "ideológico" que estamos discutindo. Provavelmente o enunciado se baseou na mesma "interpretação" que você. E assim alguns valores vão por certo divergir do que eu falei.
 

Mas o enunciado E os programas de aferição estão errados se for esse o caso. Infelizmente o autor e o site não ofereceram as strings consideradas repetidas para algum caso mais significativo, como o folclórico Mississippi ou o exemplo de 26 'a'., mas você o fez, na verdade  

 

De todo modo isso pode claro ser interpretado como você e o site fizeram. Mas ao ler a descrição no próprio enunciado fica claro que o autor se confundiu, porque cita o fato de ser um sistema de arquivos e ter cópias espalhadas pelo disco e ser a sua chance de afinal recuperar algo perdido... Eu citei isso antes.

 

Essa descrição elimina a possibilidade de aceitar 45 sequências para os 26 'a' ou 9 para Mississippi. . .

 

E eu te mostrei exemplos de situações em que isso não é aceito, coisas como o Notepad e o Chrome e o vi, e o fato de que o enunciado fala de um sistema arquivos.

 

Seria ingênuo imaginar que algum sistema de arquivos usasse uma área para uma nova versão de um arquivo que não fosse absolutamente distinta da original. É importante que você tenha isso claro: um sistema de arquivos jamais usaria um pedaço da área de uma versão anterior do arquivo para gerar a nova versão, e eu te expliquei a razão: se o usuário resolver sair sem salvar, por exemplo, o arquivo original pode ter sido corrompido. 

 

Se havia alguma ambiguidade no enunciado isso elimina o possível caráter interpretativo. É assim descrito
 

Citação

você de repente se lembrou de que o sistema de arquivos também manteve várias cópias de cada arquivo, portanto, apenas os pedaços de bytes contíguos que se repetem tem a chance de ser um arquivo. Além disso, para cada repetição dos mesmos bytes contíguos, apenas uma cópia precisa ser verificada

 

Como trataria sequências dentro delas mesmas para tentar recuperar algo? Isso seria um inferno e não levaria a nada. E é o mesmo caso para o Notepad, o vi, o Firefox. Nenhum deles aceita.

 

E você pensou que se "issi" serve como duplicata em "ississi" então deve aceitar como duplicatas a partir da segunda posição da origem, certo? Imagino que tenha feito isso em seu programa. E foi assim que o argentino autor Pablo Heiber chegou no 1377 a 45 sequências repetidas naquele exemplo de 26 'a'...

 

6 horas atrás, Simon Viegas disse:

para eu tentar entender a tua forma de interpretação... se inserir mississippi, a saída seria 8? Daí, liste cada uma dessas repetições

 

Sim de fato são 8. Para um editor de texto, para um recuperador de arquivos, ou para qualquer coisa na prática. Um exemplo simples seria no próprio IDE, por exemplo, se você usa isso: no meu ambiente tem um comando, control H. Veja o exemplo:
 

 

Para que serviria aceitar issi como duplicada se depende de "emprestar"o "i" final da sequência-alvo? Em que cenário isso seria útil?
 

No editor de texto, tipo o vi ou o sublime text, se você pedir para trocar todas as sequências, ele vai dizer ao final quantas trocou. Esse é o número que em geral a gente espera quando fala de sequências repetidas. E ele nunca considera intersecção entre o padrão e uma sequência a ser substituída.

 

"mississippi" passo a passo...

 

Como eu disse, o mais eficiente seria mesmo usar trie e uma pilha para montar as possíveis subs. A justificativa é simples: trie é uma árvore de prefixos, então conforme vai aumentando ela cresce só com o final das palavras. Se usar uma lista ligada ou um vetor de strings vai copiar tudo de novo a cada string. E isso cresce muito. mas muito rápido mesmo.

 

A questão da pilha é a seguinte: a trie é uma árvore com uma letra por nó. E N folhas para cada nó. Nesse caso aqui 64. Quando você vai "descendo" em busca de uma palavra você pode passar por outras. Imagine o caso simples do plural: se você tem verdade e verdades  então só sai faltar o 's' na segunda palavra. E aí usando uma pilha --- uma string, um char* --- você vai marcando por onde passa, como faria no papel mesmo. Cada nó que é fim de uma palavra tem uma marca então você resolve com essa técnica: uma pilha de nós.
 

Citação

É assim que os navegadores mostram a lista de sites na barra de endereços, usando trie

 

Se usar uma tabela convencional você vai ter 
 

- verdade
- verdadeiro

- verdades

Acho que já entendeu. Se usar trie vai ter "verdade", "iro" e "s" apenas...

Mas o programa aqui é simples e o orçamento é baixo: a gente escreve nas horas vagas. Depois vou postar uma solução assim com trie porque preciso tirar de algum programa ou adaptar pra ficar mais "didático" digamos.

Então como seria o simples para fazer isso?

 

Seguindo a folha de papel

 

Vamos varrer a string da esquerda para a direita

 

mississippi, 11 bytes

 a maior coisa que pode se duplicar aí é (missi)ssippi porque seria a metade. Veja o exemplo do enunciado,

    'say.twice,say.twice'

e vai entender porque um valor assim foi colocado para teste. Temos então as sequências

missi
miss
mis
mi
m

que podem ou não estarem duplicadas no arquivo

ississippi, 10 bytes
 

Temos mais essas 

issis
issi
iss
is
i

que podem ou aparecer duplicadas à direita ainda. Podem estar à esquerda, mas não importa porque se for o caso elas já aparecem na pesquisa...

ssissippi, 9 bytes

A maior duplicável é "ssis", podia aparecer como o exemplo do enunciado, tipo "ssis,ssis"

ssis
ssi
ss
s

sissippi, 8 bytes
Aqui temos

siss
sis
si
s

issippi, 7 bytes
Aqui temos

iss
is
i

ssippi, 6 bytes

Aqui temos

ssi
ss
s

sippi, 5 bytes

si
s

ippi, 4 bytes

ip
i

ppi, 3 bytes

p

pi, 2 bytes

p

i, 1 byte
 

não pode duplicar porque acabou o espaço

 

E agora?

=> 'mississippi'
missi
miss
mis
mi
m
issis
issi
iss
is
i
ssis
ssi
ss
s
siss
sis
si
s
iss
is
i
ssi
ss
s
si
s
ip
i
p
p

Essas são as possíveis 30 sequências, que podem ou não estarem duplicadas no arquivo. O simples agora seria pegar essas 30 ver quantas aparecem ao menos duas vezes no arquivo, colocar em ordem e eliminar as duplicidades. Essa foi a ideia do programa em C++ que o autor postou inicialmente.

 

Seguindo nesse rumo

Dessas 30, 12 estão de fato duplicadas no arquivo

	'iss'
	'is'
	'i'
	'ssi'
	'ss'
	's'
	'si'
	's'
	'i'
	's'
	'i'
	'p'

Colocando em ordem, o windows tem sort, o unix tem sort, grep, awk, vi...

    1   'i'
    2   'i'
    3   'i'
    4   'is'
    5   'iss'
    6   'p'
    7   's'
    8   's'
    9   's'
   10   'si'
   11   'ss'
   12   'ssi'

E eliminando os duplicados

    1   'i'
    2   'is'
    3   'iss'
    4   'p'
    5   's'
    6   'si'
    7   'ss'
    8   'ssi'

E isso você pode confirmar com qualquer editor de texto...

 

 

 

 

[Ansi C]

Nenhuma novidade é "a velha conversa"

 

Já tinha entendido, mas foi boa a revisão