Znajdź wspólny prefiks ciągu
Mam 4 struny:
"h:/a/b/c"
"h:/a/b/d"
"h:/a/b/e"
"h:/a/c"
Chcę znaleźć wspólny prefiks dla tych ciągów, czyli
„h:/a”.
Jak to znaleźć?
Zwykłem oddzielać ciąg separatorem
„/”i umieszczać go na innej liście i tak dalej.
Czy jest lepszy sposób, aby to zrobić?
Nie znaleziono powiązanych wyników
Zaproszony:
Aby odpowiedzieć na pytania, Zaloguj się lub Zarejestruj się
15 odpowiedzi
Anonimowy użytkownik
Potwierdzenie od:
od
Anonimowy użytkownik
Potwierdzenie od:
Anonimowy użytkownik
Potwierdzenie od:
Coś jak (pseudokod)
Anonimowy użytkownik
Potwierdzenie od:
Anonimowy użytkownik
Potwierdzenie od:
długi wspólny problem z podciągami
http://en.wikipedia.org/wiki/L ... oblem
(chociaż jest to trochę wyspecjalizowany przypadek, ponieważ wydaje się, że obchodzi cię tylko prefiks). W architekturze .NET nie ma biblioteki implementacji algorytmu, którą można wywołać bezpośrednio, ale artykuł, do którego prowadzi łącze, zawiera mnóstwo instrukcji dotyczących samodzielnego wykonywania tych czynności.
Anonimowy użytkownik
Potwierdzenie od:
spróbuj w c # (http://en.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Trie
Trewir).
Służy do wykonania zindeksowanego ciągu przy użyciu prefiksów. Ta klasa ma O (1) do zapisu i odczytu dla węzłów liści. W przypadku wyszukiwania prefiksu wydajność wynosi O (log n), jednak liczba wyników dla prefiksu wynosi O (1).
Oto przykład testowania jednostkowego kodu & amp; o tym, jak korzystać z tej klasy.
Wszelkie sugestie dotyczące ulepszenia tej klasy są mile widziane :)
Anonimowy użytkownik
Potwierdzenie od:
https://github.com/fschwiet/Dr ... b586f
https://github.com/fschwiet/Dr ... b586f
Anonimowy użytkownik
Potwierdzenie od:
Pobierz litera po literze, podczas gdy wszystkie inne linie mają tę samą literę na tej samej pozycji indeksu i zatrzymują się, jeśli nie ma dopasowania.
Usuń ostatni znak, jeśli jest separatorem.
Anonimowy użytkownik
Potwierdzenie od:
Jeśli istnieje więcej niż jeden prefiks o tej samej długości, zwraca losowo pierwszy znaleziony. Ponadto rozróżnia się wielkość liter. Czytelnik może wziąć pod uwagę oba te punkty!
Anonimowy użytkownik
Potwierdzenie od:
Ponieważ sprawdza tylko kilka ciągów znaków przy każdym ukośniku, będzie to nieco szybsze niż zwykła procedura prefiksu (poza moim nieefektywnym algorytmem!). Jest rozwlekły, ale łatwy do naśladowania ... mój ulubiony typ kodu ;-)
Ignoruje „http://” i „https://”, a także wielkość liter.
<pre class="lang-cs prettyprint-override">
Anonimowy użytkownik
Potwierdzenie od:
UPD:
Zaimplementowałem również wersję równoległą, która wykorzystuje powyższą metodę jako ostatni krok:
GetCommonPrefixParallel () podwaja się w porównaniu z GetCommonPrefix () na ogromnej liczbie linii i przy znacznych długościach linii. GetCommonPrefix () działa nieco lepiej na małych tablicach z krótkimi łańcuchami. Testowałem na MacBooku Pro Retina 13 ".
Anonimowy użytkownik
Potwierdzenie od:
Anonimowy użytkownik
Potwierdzenie od:
Po pierwsze, wiemy, że najdłuższy wspólny prefiks nie może być dłuższy niż najkrótszy element. Więc weź najkrótszą i weź z niej znaki, podczas gdy wszystkie inne linie mają ten sam znak w tej samej pozycji. W ostateczności bierzemy wszystkie postacie z najkrótszego elementu.
Podczas iteracji po najkrótszym elemencie wyszukiwanie indeksu nie zgłosi żadnych wyjątków.
Innym (gorszym, ale wciąż interesującym) sposobem rozwiązania tego problemu za pomocą LINQ byłby następujący:
samples.Aggregate(samples.Min(), (current, next) => new string(current.TakeWhile((c,i) => next[i] == c).ToArray() ));
Ta metoda działa poprzez utworzenie commonPrefix i porównanie go z każdym elementem jeden po drugim. W każdym porównaniu commonPrefix zostaje zachowany lub zredukowany. W pierwszej iteracji prąd jest elementem minimalnym, ale każda kolejna iteracja jest najlepszym znalezionym do tej pory commonPrefix. Potraktuj to jako rozwiązanie oparte na głębokości, podczas gdy to pierwsze jest rozwiązaniem opartym na szerokości.
Tego typu rozwiązanie można ulepszyć, sortując próbki według długości, tak aby najpierw porównywane były najkrótsze elementy.
Jednak tego typu rozwiązanie naprawdę nie może być lepsze od pierwszego. W najlepszym przypadku jest to tak dobre, jak pierwsze rozwiązanie. Ale w przeciwnym razie wykona dodatkową pracę, znajdując tymczasowe wspólne poprawki, które są dłuższe niż to konieczne.
Anonimowy użytkownik
Potwierdzenie od:
Wyjaśnienie:
params String []
zapewnia, że podano przynajmniej jeden ciąg i nie są wymagane żadne sprawdzenia w czasie wykonywania.Anonimowy użytkownik
Potwierdzenie od: