Nie jestem pewien, czy dobrze jest zwalczyć taki problem. Jeśli ktoś chce umieścić śmieci w polu aboutme, zawsze będzie wpadał na pomysł, jak to zrobić. Ale będę ignorować ten fakt i zwalczania tego problemu jako algorytmicznego wyzwanie:
uwzględniając ciąg S, która składa się z podciągów (który może pojawić wiele razy i nie pokrywających) znaleźć podciąg składać się z.
Definicja to wesz i zakładam, że ciąg jest już konwertowany na małe litery.
Pierwszy prostszy sposób:
Zastosowanie modyfikacja longest common subsequence który ma proste rozwiązanie programowania DP. Ale zamiast znajdować podsekcję w dwóch różnych sekwencjach, można znaleźć najdłuższy wspólny podciąg ciągu w odniesieniu do tego samego ciągu LCS(s, s).
Na początku brzmi głupio (z pewnością LCS(s, s) == s), ale w rzeczywistości nie zależy nam na odpowiedzi, zależy nam na macierzy DP, którą otrzymujemy. wygląd
Miejmy na przykład: s = "abcabcabc" i matryca jest:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 2, 0, 0, 2, 0, 0, 2, 0]
[0, 0, 0, 3, 0, 0, 3, 0, 0, 3]
[0, 1, 0, 0, 4, 0, 0, 4, 0, 0]
[0, 0, 2, 0, 0, 5, 0, 0, 5, 0]
[0, 0, 0, 3, 0, 0, 6, 0, 0, 6]
[0, 1, 0, 0, 4, 0, 0, 7, 0, 0]
[0, 0, 2, 0, 0, 5, 0, 0, 8, 0]
[0, 0, 0, 3, 0, 0, 6, 0, 0, 9]
Uwaga ładne przekątne tam. Jak widać pierwsze przekątne kończy się na 3, drugie na 6 i na trzecim z 9 (nasze oryginalne rozwiązanie DP, którego nie obchodzi).
To nie jest zbieg okoliczności. Mam nadzieję, że po dokładniejszym przeanalizowaniu budowy matrycy DP można zauważyć, że przekątne odpowiadają zduplikowanym ciągom znaków.
Oto przykład dla s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas" 
oraz bardzo ostatni wiersz w macierzy jest: [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 17, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 34, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 51, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 68].
Jak widać duże liczby (17, 34, 51, 68) odpowiadają końcowi przekątnych (jest tam także trochę szumu, ponieważ specjalnie dodałem małe duplikaty, takie jak aaa).
Które sugerują, że możemy po prostu znaleźć gcd z największych dwóch liczb gcd(68, 51) = 17, które będą długości naszego wielokrotnego podciągu.
Tylko dlatego, że wiemy, że cały ciąg składa się z powtarzających się podciągów, wiemy, że zaczyna się on od 0-tej pozycji (jeśli nie wiemy, musimy znaleźć offset).
I oto: ciąg znaków to "aaabasdfwasfsdtas".
P.S. Ta metoda pozwala znaleźć powtórzenia, nawet jeśli są nieznacznie zmodyfikowane.
Dla osób, które chciałyby się bawić o to skrypt Pythona (który powstał w pośpiechu więc nie krępuj się poprawić):
def longest_common_substring(s1, s2):
m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
longest, x_longest = 0, 0
for x in xrange(1, 1 + len(s1)):
for y in xrange(1, 1 + len(s2)):
if s1[x - 1] == s2[y - 1]:
m[x][y] = m[x - 1][y - 1] + 1
if m[x][y] > longest:
longest = m[x][y]
else:
m[x][y] = 0
return m
s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas"
m = longest_common_substring(s, s)
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
M = np.array(m)
print m[-1]
arr = np.asarray(M)
plt.imshow(arr, cmap = cm.Greys_r, interpolation='none')
plt.show()
Mówiłem o łatwy sposób, a Zapomniałem pisać o trudnej drodze. Robi się późno, więc wyjaśnię ten pomysł. Wdrożenie jest trudniejsze i nie jestem pewien, czy da lepsze wyniki. Ale tutaj jest:
Użyj algorytmu dla longest repeated substring (będziesz musiał zaimplementować trie lub suffix tree co nie jest łatwe w php).
Po tym:
s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas"
s1 = largest_substring_algo1(s)
Took realizację largest_substring_algo1 from here. W rzeczywistości nie jest najlepszy (tylko do pokazania idei), ponieważ nie korzysta z wyżej wymienionych struktur danych. Wyniki dla s i s1 są:
aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas
aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaa
Jak widać różnica między nimi jest właściwie podciąg, który został powielony.
Powiązane: http://venturebeat.com/2015/07/26/watch-this-brilliant-visualization-of-words-in-the-angielski-language/ –
Nie próbuję krytykować podejścia (wiem, że to będzie działać świetnie). Ale tutaj jest kilka pytań: 1) w jaki sposób można znaleźć duplikat frazy (tak, to składa się z n-słów, które znaleźliśmy, ale są n! Różne możliwości). 2) co byś zrobił, gdyby osoba napisała tekst bez spacji. –