Удалить повторяющиеся строки из строки

Question

Я хотел попробовать создать алгоритм для удаления повторяющихся строк в строке.

Например

Входной сигнал: Привет Выход: Helo

Вход: AAAAZZZZ5 Выход: AZ5

Входной сигнал: "яблоки и яблоки и апельсины" Выходные: "Яблоки и апельсины"

Я написал алгоритм ниже (JSFiddle here)

function removeRepeat(str) 
{ 
    var index = 0; 
    var tempS = str.length; 
    var currentBuffer = ""; 
    var repeatCharIndex = 1; 
    console.log(str); 
    for (var i = 1; i < tempS; i++) 
    { 
     var curChar = str[i]; 
     for (var j = 0; j < i; j++) 
     { 
      // check if duplicate 
      if (str[j] === curChar) 
      { 
       console.log("duplicate detected at index ",j,str[j],"and index",i,str[i]) 
       // we have duplicate! means we could potentially have a repeated set of characters 
       // i, j have same character, so let's move both forward 
       var aheadLeft=j, aheadRight=i; 
       var diff = Math.min(aheadRight-aheadLeft,tempS-aheadRight); 
       var repeat = true; 
       for (var num = 1; num < diff; num++) 
       { 
        // we go backwards... 
        // ashiash ... 
        // we are at __h___h, so now we go 
        // _s__s_ 
        console.log("\tis ",str[aheadRight+num],str[aheadLeft+num]) 
        if (str[aheadRight+num] !== str[aheadLeft+num]) 
        { 
         repeat = false; 
         break; 
        }  
       } 
       if (repeat){ 
        console.log("found repeat!",str,str[aheadLeft],aheadLeft,str[aheadRight],aheadRight); 
        str = str.substring(0,aheadRight)+str.substring(aheadRight+diff) 
        return removeRepeat(str); 
       } 
       break; 
      } 
     } 
    } 
    return str; 
} 
console.log("New str: "+removeRepeat("nnnnnnnnzzzzzz1")); 

Проблема у меня в том, что алгоритм не дает правильный результат для "Apples and Apples and Oranges"

Неоднократное строка должна быть Apples and и результат должен быть яблоки и апельсины, но я получаю

Aples and Apples and Orang 

Я не уверен, как исправить мой алгоритм, чтобы проверить, является ли дубликат частью более крупного изображения. Одна из моих идей заключалась в том, чтобы вернуться назад, а не вперед по струне. Любые идеи/советы были бы замечательными!

* Редактировать: Я не был достаточно ясен в своих оригинальных примерах.

Входной Hey Hi Hi Hi Hey Hi Hi Hi должен выводить Hey Hi Hi Hi, а не Hey Hi потому что Hi Hi Hi, повторяя, является частью большего Hey Hi Hi Hi

Boots and Cats and Boots and Cats and YO должна равняться Boots and Cats Yo не Bots and Cats and Boots and Cats and YO

Answer 1

то, что я предлагаю вам сделать, это написать функцию, которая удаляет длинный дубликат, а затем назовите его несколько раз, если вам это нравится. это самый простой способ увидеть, как удалить (большую часть) двусмысленность в спецификации.

, и если вы хотите это сделать, возьмите код, который у вас есть, но вместо фактического удаления кода просто отследите, сколько будет удалено, и где. каждый раз, когда вы найдете способ удалить больше, обновите эту информацию.

Затем, в конце, удалите самый большой найденный фрагмент (информация, которую вы сохранили).

Answer 2

Это будет очень близко к тому, что вы просите. Я думаю, что два из ваших примеров требуют незначительных изменений, но без них они, похоже, не имеют смысла.

В Javascript,

str.replace(/(.+?)(\1)+/g, function(match, group){return group;}) 

Что мы делаем здесь соответствует строковое (группа 1), а затем сам один или несколько раз, и заменить его только в одном случае. Соревнование группы 1 не является жадным, так что AAAA ->A вместо AA.

Тестовые:

1) "Apples and Apples and Oranges" -> "Apples and Oranges" 
2) "Hey Hi Hi Hi Hey Hi Hi Hi" -> "Hey Hi Hey Hi" 
3) "Hey Hi Hi Hi Hey Hi Hi Hi " -> "Hey Hi Hi Hi " 
4) "Boots and Cats and Boots and Cats and YO" -> "Boots and Cats and YO" 
5) "AAAAZZZZ5" -> "AZ5" 

Обратите внимание, что 2) не соответствует вопрос, но для этого нужно, что пространство для того, чтобы повторения, который вы ищете, чтобы быть на самом деле есть. Я думаю, 3) показывает, что он решает этот случай, как и следовало ожидать.

4) не совсем подходит, но, думаю, это опечатка в вопросе.