Jak zliczyć z dwuwymiarowej tablicy najczęsciej wystepujący ciąg znaków

0

Zastanawiam się nad najszybszym i prostym algorytmem do zliczenia który wiersz znaków w tablicy występuje najczęściej ( możliwe znaki do wystąpienia a,b,c,d )
np:

a
abc
abcd
abc
aaa
b
b
aaabcd
abcd
abcd

tutaj najczęściej występuje wiersz abcd, i teraz załóżmy że mam długie ciągi znaków i więcej wierszy. Mój pomysł na chwile obecną to: zacząć od 1 znaku, jeśli po nim nie występują żadne nastepne znaki to zliczać ile jest a ile b ile c ile d i zostawiać ten najdłuższy z jednego znaku, przejść do wierszy gdzie wystepuje wiecej niż jeden znak i tak samo zliczać i później porównywać ile jest najwięcej z jednego znaku ile z dwóch znaków i dalej iść do wierszy składających się z 3 znaków. Macie lepszy pomysł? :D

0

Posortuj i przechodząc tablicę licz ile jest takich samych.

0

j.w. albo map<string, int>

0

a jakie sortowanie byłoby najkorzystniejsze?

0

@Michał Nadrocki: w C++ po prostu uzyj std::sort. Z reguly najszybsze bedzie quick sort ale w pesymistycznym przypadku heap sort bedzie lepsze (w C++ jesli dobrze pamietam to sort zacznie robic quick sorta, ale jak zauwazy ze jest pesymistyczny przypadek to zmieni na heap sort. Introsort chyba?).

0

ok dzięki za pomoc ;) a przeczytałem, że jakieś bucket sort II ma złożoność czasową O(n) czy to jest to zaimplementowania?

1

W tym przypadku unordered_map będzie trywialne i da ci też O(n). Iterujesz po danych i wrzucasz do mapy. Jeśli już taki wpis w mapie jest, to wpisujesz poprzednia_wartość+1, a jak jeszcze nie ma to wpisujesz z wartością 1.

0

a jeśli chciałbym to zrobić bez użycia map? i dodam że sortowanie nie wchodzi w grę bo nie dodałem, że kolejność znaków ma znaczenie. abcb to jest co innego niż abbc

1

Poczekaj, dla podanych przez Ciebie danych jaki powinien być wynik? Bo widzę, że jest coś zamotane. Bo z jednej strony mówisz, że chcesz liczyć ciągi znaków a potem mówisz coś o pojedynczych znakach. Zdecyduj się.

0

Naiwnie to będzie tak:

fun frequencies(xs):
	limit = length(xs)
	freq = [-1, -1, ...] limit times
	for i = 0 to limit - 1:
		count = 1
		for j = i + 1 to limit - 1:
			if xs[i] == xs[j]:
				count += 1
				freq[j] = 0
		if freq[i] != 0:
			freq[i] = count
	for i = 0 to limit - 1:
		if freq[i] != 0:
			print(xs[i] + " has frequency: " + freq[i])

Złożoność jest słaba O(n^2), lepiej użyć, jak sugerują powyżej, mapy, lub wbudowanych w język bibliotek: Collections.frequency w Javie, collections.Counter w Pythonie.

0
Michał Nadrocki napisał(a):

a jeśli chciałbym to zrobić bez użycia map? i dodam że sortowanie nie wchodzi w grę bo nie dodałem, że kolejność znaków ma znaczenie. abcb to jest co innego niż abbc

Policz hash code dla każdego elementu, zachowaj na boku kopię X, posortuj te kody i zlicz najdłuższy ciąg takich samych kodów. Potem wykorzystaj kopię X w celu znalezienia ciągu znaków dla którego znalazłeś hash code.

Wada tego rozwiązania: trzeba policzyć hash code dla każdego ciągu w całości, nawet jeśli wszystkie różnią się np. na pierwszych 5 znakach.
Czyli złośliwy przypadek to będzie tablica losowych ciągów, każdy o długości zbliżonej lub większej niż liczba ciągów.

1 użytkowników online, w tym zalogowanych: 0, gości: 1