 |
Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
smas
Okrutny Admin
Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów
|
 Wysłany: Pią 5:29, 08 Gru 2006 Temat postu: Zadanie Z1 - Aho-Corasick |
|
|
[link widoczny dla zalogowanych]
"Nowe zadanie - nieobowiązkowe i niepunktowane. Jego cel to umożliwienie zaimplementowania i zdebugowania algorytmu Aho-Corasick, który się przyda w zadaniu T."
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kg86
zielony żul
Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów
Skąd: pochodze?
|
| Wysłany: Pią 12:40, 08 Gru 2006 Temat postu: |
|
|
|
brzmi groznie :P z tym ze Aho-Corasick w Z1 jest trudniejszy od tego ktory bedzie trzeba wykorzystac w T...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
smas
Okrutny Admin
Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów
|
| Wysłany: Pią 13:53, 08 Gru 2006 Temat postu: |
|
|
| kg86 napisał: | | brzmi groznie :P z tym ze Aho-Corasick w Z1 jest trudniejszy od tego ktory bedzie trzeba wykorzystac w T... |
ale jaka przyjemność... no i całkowicie za darmo - tylko w TCSie, TCS nie dla idiotów;]
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Roxel
pijak
Dołączył: 06 Kwi 2006
Posty: 249
Przeczytał: 0 tematów
Skąd: Pszczyna
|
| Wysłany: Pią 22:49, 08 Gru 2006 Temat postu: |
|
|
| smas napisał: | | TCS, nie dla idiotów |
Nieźle to brzmi :D Powinieneś im sprzedać to hasło reklamowe :idea:
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Source
pijak
Dołączył: 26 Paź 2005
Posty: 92
Przeczytał: 0 tematów
Skąd: Zmc
|
| Wysłany: Nie 18:00, 10 Gru 2006 Temat postu: |
|
|
Mógłby ktoś zapodać binarkę? :wink:
Bo ANSa łapię.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Prezioso
pijak
Dołączył: 18 Lis 2005
Posty: 100
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Nie 19:00, 10 Gru 2006 Temat postu: |
|
|
|
[link widoczny dla zalogowanych]
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Nie 20:43, 10 Gru 2006 Temat postu: |
|
|
|
Jakby coś, to mateo uruchomił testerkę dla Z1 w trybie TEST_FINDER ;) .
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Pon 16:07, 18 Gru 2006 Temat postu: |
|
|
Kurde, nęka mnie RTE tutaj i nie mam pomysłu :?
Jeszcze chwilka i na TCS się ogłoszę :?
U Mateo mam:
| Kod: | ID TEST LIMIT CZAS WYNIK STATUS
1 1 3.40s 0.16s 0/10 S06 (SIGABRT - Abort) |
Ściągnąłem sobie ten test do siebie i u mnie plik wynikowy jest taki sam jak 1.out (ten Mateowy). Nie wiem już nic :(
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Pon 16:15, 18 Gru 2006 Temat postu: |
|
|
|
SIGABRT może być spowodowany wyczerpaniem pamięci poprzez za częste wywołania new. Sprawdź czy masz dobre czyszczenie.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Pon 16:28, 18 Gru 2006 Temat postu: |
|
|
| Spectro napisał: | | SIGABRT może być spowodowany wyczerpaniem pamięci poprzez za częste wywołania new. Sprawdź czy masz dobre czyszczenie. |
| Kod: | void deleteAll( Node* node )
// zwalnia pamiec po drzewie Aho - Corasick
{
for( i = 0 ; i < LETTERS ; ++i )
{
if( node->letters[ i ] != NULL )
{
deleteAll( node->letters[ i ] );
};
};
delete node;
}; |
Ja tu nic nie znalazłem, u mnie wszystko śmiga, ale nie umiem sobie ustawić ograniczenia pamięci :/ da się w Win w ogóle :?:
new jest często wywoływany, bo każdą literkę przecież trzeba jakoś wmontować do drzewka Aho...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
r4ku
żul
Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów
Skąd: klikash? :D
|
| Wysłany: Pon 16:58, 18 Gru 2006 Temat postu: |
|
|
sproboj moze przeladowac sobie operatory new i delete i wprowadz statystyke urodzin ;) zobaczysz czy wszystko jest prawidlowo czyszczone
ja mialem ten blad przy avlach jak probowalem je do zadania P podpiac, ale nie udalo mi sie go wyeliminowac zanim nie stracilem cierpliwosci... dlatego aho juz robilem na statycznej tablicy :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
smh
[świeżak]
Dołączył: 05 Mar 2006
Posty: 21
Przeczytał: 0 tematów
|
| Wysłany: Pon 20:33, 18 Gru 2006 Temat postu: |
|
|
| Prezioso napisał: | | http://www.ii.uj.edu.pl/~hruby/z1.exe |
Czy ten program przeszedł? Bo męczę się nad tym zadankiem od rana i dostałem dwa razy TLE, chociaż mój program chodzi szybciej od tego wyżej wymienionego.
I jeszcze jedna sprawa - próbował ktoś może działać na testach typu:
tekst: 10000 literek "a"
3147 wzorcow: kazdy zbudowany tylko z literek "a" o dlugosciach od 1 do 3147
coś takiego idzie mi dwie minuty, więc zastanawiam się czy przypadkiem nie zapomniałem o jakiejś optymalizacji, dla testow z wzorcami wielokrotnie się w sobie zawierających...
za każdego hinta z góry dziękuję :)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Pon 20:51, 18 Gru 2006 Temat postu: |
|
|
edit: Pochrzaniły mi się zadania ;] . Nieważne.
Ostatnio zmieniony przez Spectro dnia Pon 23:15, 18 Gru 2006, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
dzendras
Germański oprawca
Dołączył: 07 Mar 2006
Posty: 1326
Przeczytał: 0 tematów
Skąd: Chorzów
|
| Wysłany: Pon 21:04, 18 Gru 2006 Temat postu: |
|
|
@smh: musisz zrobić shortcuty, czyli dla każdego wzorca musisz pamiętać wzorzec będący jego najdłuższym właściwym sufiksem. I przy wypisywaniu wzorca, nie idziesz potem rekurencyjnie po failach, tylko po shortcutach (troszkę to ogranicza skakanie po pamięci :lol: )
Jeśli jednak piszesz Z1 pod kątem zadania T, to tą optymalizację możesz sobie darować (w bakerze taka sytuacja nie występuje)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Pon 21:25, 18 Gru 2006 Temat postu: |
|
|
Kurwa, jestem debilem (znowu :evil:)
Używałem globalnego iteratora w rekurencyjnym czyszczeniu drzewa :!:
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
oinopion
żul
Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Pon 21:36, 18 Gru 2006 Temat postu: |
|
|
| Skrobocik napisał: | | Kurwa, jestem debilem |
tez mi nowina :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Pon 21:46, 18 Gru 2006 Temat postu: |
|
|
| Skrobocik napisał: | | Kurwa, jestem debilem |
Zawsze ci to powtarzalem...dobrze chociaz ze juz dojrzales zeby sie do tego publicznie przyznac...jestem z ciebie dumny :D
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kafex
zielony żul
Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów
Skąd: Zawiercie
|
| Wysłany: Pon 22:56, 18 Gru 2006 Temat postu: |
|
|
|
nie po raz pierwszy ;]
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Wto 1:04, 19 Gru 2006 Temat postu: |
|
|
|
Ale jesteście chujki - kopać leżącego :? ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Wto 1:30, 19 Gru 2006 Temat postu: |
|
|
| Skrobocik napisał: | | Ale jesteście chujki - kopać leżącego :? ;) |
Tak jest przeciez najprzyjemniej - co za frajda kopac stojacego? A nuz nie daj boze odda... ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
smh
[świeżak]
Dołączył: 05 Mar 2006
Posty: 21
Przeczytał: 0 tematów
|
| Wysłany: Wto 2:01, 19 Gru 2006 Temat postu: |
|
|
|
@dzendras: Wielkie dzięki! Teraz działa, tak jak powinno.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
urban
pijak
Dołączył: 12 Maj 2006
Posty: 109
Przeczytał: 0 tematów
|
| Wysłany: Pon 17:22, 25 Gru 2006 Temat postu: |
|
|
Mam pytanie w jakiej strukturze przechowujecie wzory? jak je wczytujecie? Mam pare pomyslow ale nie dzialaja:
1. Jako tablice lancuchow znakow, ale nie wiem jak dlugie tworzyc te lancuchy.
2. Jako jedna tablice znakow, ale nie wiem jak pozniej je oddzielac i jak wybierac miejsce w ktore mam wczytac. Jest jakas funkcja w cpp ktora wczytuje lancuch i wzraca ilosc wczytanych znakow?
Z gory dzieki za pomoc
ps. Moze od razu po wczytaniu pojedynczego tworzycie z niego drzewo?
ps2. Drzewo tworzycie dynamicznie? Galezie trzymacie jako liste?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
r4ku
żul
Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów
Skąd: klikash? :D
|
| Wysłany: Pon 18:33, 25 Gru 2006 Temat postu: |
|
|
ja wczytuje scanfem jako string - %s i odrazu laduje do drzewka,
strlen() zwraca dlugosc stringa.
| Kod: | char wzorzec[5000001];
scanf("%s",&wzorzec);
long dlugosc = strlen(wzorzec);
|
takze drzewka jest tworzone na birzaco. trzymam je w tablicy statycznej jako drzewko kursorowe, kazdy wierzcholek zawiera tablice 25 synow (sa to indeksy werzcholkow w tablicy) rownie dobrze mozna trzymac na wskaznikach trzeba tylko wtedy pilnowac alokowania i zwalniania pamieci.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Pon 20:34, 25 Gru 2006 Temat postu: |
|
|
| Kod: | scanf("%d%s", &n, t+1);
tn = strlen(t+1);
for(int i=1; i<=n; ++i) {
scanf("%s", p+pn[i-1]+1);
pn[i] = pn[i-1]+strlen(p+pn[i-1]+1);
} |
Hmmm... chyba trochę przekombinowałem, ale działa :P .
| r4ku napisał: | | tablice 25 synow |
Chyba 26 ;) .
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
r4ku
żul
Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów
Skąd: klikash? :D
|
| Wysłany: Pon 20:54, 25 Gru 2006 Temat postu: |
|
|
| Spectro napisał: | | r4ku napisał: | | tablice 25 synow |
Chyba 26 ;) . |
25 w sensie 0..25 :P
|
|
| Powrót do góry |
|
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
