Recuperação de arquivos

Programação C e C++
#1

Sua escola tem um computador que é usado como um servidor web para hospedar seu site institucional, páginas pessoais dos funcionários, sites para grupos de pesquisa, assuntos, e muitos outros. Recentemente, a tabela do disco rígido foi corrompida, por isso a organização de todos os arquivos foi perdida. Infelizmente, não há backups dessas informações. A única esperança é olhar através de todo o disco de dados e tentar descobrir quais partes correspondem a cada arquivo. Felizmente, o disco foi usando um sistema de arquivos que manteve cada arquivo contíguo, apenas as partes contíguas de dados precisam ser inspecionadas.

Os dados do disco é uma seqüência de bytes. Cada byte neste disco em particular pode armazenar uma letra do alfabeto Inglês (maiúsculas e minúsculas distintas), um dígito decimal, um ponto ou uma vírgula, totalizando 64 caracteres diferentes.

Enquanto você estava pensando em como resolver o problema, 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. Por exemplo, se os dados forem ‘ababcabb’, as subsequências repetidos contíguas são ‘a’, ‘b’ e ‘ab’, mas nada que contenha ‘c’, nem ‘ba’ ou ‘Bb’ é. Portanto, temos 3 pedaços de bytes contíguos que precisam de verificação neste caso. Você precisa escrever um programa que calcule exatamente 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.

Entrada

Há diversos casos de teste. A entrada de cada caso de teste é dada em exatamente uma linha, contendo uma string não-vazia de no máximo 105 caracteres que representa os dados do disco. Cada caractere da string poderá ser uma letra minúscula, uma letra maiúscula, um dígito, um ponto ou uma vírgula. O último caso de teste é seguido por uma linha contendo um único asterisco.

Saída

Para cada caso de teste, seu programa deverá retornar uma linha com um inteiro, representando o número de diferentes subsequências contíguas que aparecem pelo menos duas vezes na seqüência de entrada.

#2

Boa questão, mostre-nos o que já fez. Não resolvemos lição de casa.

3 curtidas
#4 
#include <stdio.h>
#include<stdlib.h>
#include <string.h>
int bruteSearch(char *txt, char *pat);
void substring(char s[], char sub[], int p, int l);

int bruteSearch(char *txt, char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);
    int i;
    for (i=0; i<=N; i++){
        int j;
        for (j=0; j<M; j++){
            if(txt[i+j]!=pat[j]){
                break;
            }
        }
        if (j==M){
            return i;
        }
    }
    return -1;
}

void substring(char s[], char sub[], int p, int l) {
    int c = 0;
    int pos=c+l;
    while (c < pos) {
        sub[c] = s[p+c-1];
        c++;
    }
    sub[c] = '\0';
}

int main(int argc, char **argv){
	int i; int numero; int z;
	int vetor[10] = {0};

 	scanf("%d", &numero);
 	char s[201]={'\0'};

 		for(z=0; z<numero; z++){
 			scanf("%s", s);
 				for(i=0; i<strlen(s); i++)
 					vetor[s[i]-'0']++;
	}
 		printf("%d %d\n", i, vetor[s]);
}
#5

@observadoranonimo não entendi a ignorância sendo que o tópico não estava mencionando o seu nome diretamente.

Já foi falado uma vez, você não precisa falar besteira desnecessáriamente.

Trate os colegas com respeito.

1 curtida
#6

Fiz esse exemplo, acho que ele atende todos os caso de teste:

#include <iostream>
#include <cstdio>
#include <string.h>
#include <stdlib.h>

using namespace std;

bool chaveJaUsada(string chave, string *chavesArray, int t){
  for(int i = 0; i<t; i++){
    if(chave.compare(chavesArray[i]) == 0){
      return true;
    }
  }
  return false;
}            

int contarSequencia(string texto){
  
  //Explicação #1
  int tamanho = texto.length();
  int maxComprimento = tamanho/2;
  int total = 0;
  
  for(int i = 1; i<=maxComprimento; i++){
    
    //Explicação #2
    int tamanhoArray = (tamanho - (i-1));
    string *chavesArray = new string[tamanhoArray];
    int k = -1;
    
    for(int j = 0; j<=(tamanho-i); j++){
      
      //Explicação #3
      string chave = texto.substr(j,i);
      bool jaUsada = chaveJaUsada(chave,chavesArray,tamanhoArray);               
     
      if(jaUsada == false){
        
        //Explicação #4
        string textoBusca = texto.substr(j+i, tamanho-(j+i));
        size_t found = textoBusca.find(chave);
      
        if(found != string::npos){
          total++;
          k++;
          chavesArray[k] = chave;
        }
        
      }
    }
    //libero a memoria;
    delete[] chavesArray;
  }
  return total;
}

//Método Main \ö/
int main() {
  
  string texto;
  cin >> texto;
  
  int total = contarSequencia(texto);
  
  cout << "total: "<< total << endl;
  return 0;
}

#1
Pelo o que eu entendi o problema consiste em encontrar a ocorrência de varias palavras chaves em uma String, então o primeiro passo é calcular o tamanho máximo da palavra chave (maxComprimento). Exemplo com a String ababcabb:

Possiveis palavras chaves:
a, b, c, ab, ba, bc, ca, bb, aba, bab, abc, bca, cab, abb,
abab, babc, abca, bcab, cabb.

Então o comprimento máximo é o piso do tamanho da string/2, pois maior do que isso não “cabe” uma nova ocorrência! Para gerar todas essa palavras são os dois for, o i é o comprimento e o j o ponto de partida!

#2
Apenas crio um array com todas as palavras chaves do mesmo tamanho!

#3
Uso a função substr para pegar as palavra chaves, e chamo a função chaveJaUsada para verificar como base no array que criei se essa já foi processada, se sim, apenas a ignoro e vou para próxima.

#4
Aqui eu pego o meu texto de busca, sempre olhando para frente (uma posição a frente da palavra chave), exemplo:
String: ababcabb
Com a chave: a
Texto de Busca: babcabb

Para fazer a busca uso o método find() da string
Se for encontrada eu Incremento mais 1 ao meu total e adiciona a palavra ao array de palavras chaves já processadas!

Essa foi a lógica que conseguir pensar, mas como você pode perceber pelo número de palavras chaves, não é muito eficiente, além disso é necessário ficar verificando se uma já foi processada!
A um tempo atrás me deparei com um problema semelhante a esse, cuja a solução era baseada nos algoritmos Aho Corasick ou Sufix Arrays que realiza uma busca de um conjunto de palavras em uma String com uma performance muito boa. Mas esses algoritmos não são nada fácil de serem implementados (pelo menos para mim!).

#7

Apenas para completar esses foram os teste que fiz:

Entrada:                   Saida:
ababcabb                   Total: 3
abababa                    Total: 5
abc                        Total: 0
f                          Total: 0
..,,a                      Total: 2
aaaaaaa                    Total: 3
abcdfgtyuojllpo            Total: 2