Encontrar conteúdo duplicado na string?

Como você resolveria o seguinte problema:

Eu tenho um arquivo semi-grande com texto (cerca de 10 páginas) e quero encontrar conteúdo duplicado neste texto. Para ser mais específico, dada uma string, encontre as duas strings mais longas que são idênticas.

Eu estive olhando para a mais longa subsequência comum:

http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence

Mas essas implementações usam duas strings como input.

Talvez haja um serviço já fazendo isso?

Aqui está um algoritmo simples (mas ineficiente): Realça todos os possíveis comprimentos de subcadeia, desde o máximo até 1. Para cada comprimento, coloque todas as subseqüências desse comprimento em um dictionary. Se você encontrar uma duplicata, pare. Deve ser o maior deles. Aqui está o código C # correspondente:

public static string FindDuplicateSubstring(string s) { for (int len = s.Length-1; len > 0; len--) { var dict = new Dictionary(); for (int i = 0; i <= s.Length - len; i++) { string sub = s.Substring(i, len); if (dict.ContainsKey(sub)) return sub; else dict[sub] = i; } } return null; } 

Por exemplo, quando aplicada ao texto da sua pergunta, a substring repetida mais longa é "implementação". Note que substrings sobrepostas são permitidas, isto é, a input "bbbb" retorna "bbb". Não ficou claro em sua pergunta se você queria excluir o caso sobreposto. Para uma abordagem mais rápida, veja minha outra resposta.

O algoritmo “Maior subseqüência comum” não requer que as correspondências sejam substrings contíguas. Por exemplo, para as strings “computer” e “houseboat”, a subsequência é “out”. É isso que voce quer?

Se você quiser que as correspondências sejam substrings contíguas, isso é chamado de o maior problema de subseqüência de caracteres . O link descreve um algoritmo linear de tempo e espaço usando trees de sufixos.

Se você quer algo curto e simples, aqui está uma abordagem baseada no algoritmo LCS, mas sem uma tabela. A idéia é fazer o loop de todos os deslocamentos de números inteiros possíveis entre a substring desejada e sua duplicata. Para cada turno, encontre a maior correspondência contígua, varrendo a string uma vez. Se a string de input tiver comprimento n, haverá O (n) possíveis mudanças e verificar se cada deslocamento leva O (n) tempo, de modo que o custo total seja O (n ^ 2), com apenas uma quantidade constante de espaço. (Compare com a minha simples resposta de dictionary que toma O (n ^ 3) hora e O (n ^ 2) espaço.) Se você não quer coincidir com sobrepostas (ou seja, você quer que “bbbb” retorne “bb” não “bbb” ), então, ao verificar cada turno, você para quando a maior correspondência excede o turno. Aqui está o código C #:

  public static string FindDuplicateSubstring(string s, bool allowOverlap = false) { int matchPos = 0, maxLength = 0; for (int shift = 1; shift < s.Length; shift++) { int matchCount = 0; for (int i = 0; i < s.Length - shift; i++) { if (s[i] == s[i+shift]) { matchCount++; if (matchCount > maxLength) { maxLength = matchCount; matchPos = i-matchCount+1; } if (!allowOverlap && (matchCount == shift)) { // we have found the largest allowable match // for this shift. break; } } else matchCount = 0; } } if (maxLength > 0) return s.Substring(matchPos, maxLength); else return null; } 

Eu testei isso contra a resposta do meu dictionary e dá os mesmos resultados. Mas para uma seqüência aleatória de comprimento 3000, o dictionary leva 15 segundos, enquanto o método acima leva 60ms (e muito menos memory).

tente isso

 public static string FindLargestDuplicateString( string text) { var largest = string.Empty; for (var i = '!'; i <= '}'; i++) { var l = FindLargestDuplicateStringImpl( text, i.ToString()); if (l.Length > largest.Length) largest = l; } return largest; } private static string FindLargestDuplicateStringImpl( string text, string currentLargest) { bool found = false; for (var i = '!'; i <= '}'; i++) { var comp = currentLargest + i; var last = text.LastIndexOf(comp); var first = text.IndexOf(comp, 0); if (first == -1 || last == -1 || first == last) continue; currentLargest = comp; found = true; } return !found ? currentLargest : FindLargestDuplicateStringImpl(text, currentLargest); } 

Você pode fazer algo assim

 public static ArrayList split(String line){ line+=" "; Pattern pattern = Pattern.compile("\\w*\\s"); Matcher matcher = pattern.matcher(line); ArrayList list = new ArrayList(); while (matcher.find()){ list.add(matcher.group()); } return list; } 

não se esqueça de remover qualquer pontuação

 public static void duplicatedWords(String s, int n){ ArrayList splitted = split(s); System.out.println(splitted); HashMap map = new HashMap(); PriorityQueue pq = new PriorityQueue(splitted.size(), new myComp()); for(int i = 0; i 

Com este comparador:

 public static class myComp implements Comparator{ @Override public int compare(Object arg0, Object arg1) { String s1 = (String)arg0; String s2 = (String)arg1; return s2.length()-s1.length(); } }