abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 12:00 | Zajímavý projekt

Projekt Termbox umožňuje vyzkoušet si linuxové distribuce Ubuntu, Debian, Fedora, CentOS a Arch Linux ve webovém prohlížeči. Řešení je postaveno na projektu HyperContainer. Podrobnosti v často kladených dotazech (FAQ). Zdrojové kódy jsou k dispozici na GitHubu [reddit].

Ladislav Hagara | Komentářů: 0
dnes 11:00 | Bezpečnostní upozornění

Byly zveřejněny informace o bezpečnostní chybě CVE-2016-8655 v Linuxu zneužitelné k lokální eskalaci práv. Chyba se dostala do linuxového jádra v srpnu 2011. V upstreamu byla opravena minulý týden [Hacker News].

Ladislav Hagara | Komentářů: 0
včera 22:00 | Komunita

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 5
včera 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 31
včera 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 9
3.12. 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 17
3.12. 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 25
2.12. 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 17
2.12. 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 5
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 774 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Hledání nejdelší symetrické části řetežce

Arses avatar 21.11.2006 21:37 Arses | skóre: 4 | blog: arses
Hledání nejdelší symetrické části řetežce
Přečteno: 164×
Zdravim, potřeboval bych poradit s tímto problémem, jak najít nejdelší symetrickou část (třeba 1235555321) a podobně. Potřebuju co nejméně časově náročnou verzi, napadlo mě jenom toto:
.
.
delka = 1;
for (i = 0; i < n-1; i++)
   for (j = i+1; j < n; j++) {
      sym = 1;
      for (k = 0; i+k < j-k; k++)
         of (a[i+k] != a[j+k])
             sym = 0;
      if (sym && (j-i+1 > delka))
         delka = j-i+1;
    }
.
.
.
A to je časově poměrně dost náročný

Jinak n je délka řetězce a délka je velikost onoho nejdelšího úseku... ostatní je jasný bych řekl...

Díky moc za každou radu

Odpovědi

Arses avatar 21.11.2006 22:14 Arses | skóre: 4 | blog: arses
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Ještě dodám, že nezáleží na jazyku, jde mi čistě jen o ten algoritmus, C sem vzal jenom jako příklad...
21.11.2006 22:48 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
To je domácí úkol nebo nějaká soutěž?
Arses avatar 22.11.2006 07:04 Arses | skóre: 4 | blog: arses
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Ani jedno, domácí úkol byl napsat to... to sem udělal, ale nejsem s tim spokojenej....
Matyáš Dvořák avatar 21.11.2006 22:58 Matyáš Dvořák | skóre: 13
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
asi bych pouzil neco ve stylu grep '^\(.\)\(.\).\2\1$' soubor
21.11.2006 23:03 moira | skóre: 30 | blog: nesmysly
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/

Zacatek + odstavecek o hledani palindromu. Muzete dosahnout narocnost O(n) ;)
Překladač ti nikdy neřekne: "budeme kamarádi"
Arses avatar 22.11.2006 07:07 Arses | skóre: 4 | blog: arses
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Díky moc, jdu se tim prokousat ;-)
22.11.2006 12:17 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
#include <stdio.h>

int main(int argc, char **argv) {
	char *start, *end, *lpos, *i, *j;
	int lhalf = 0;
	if (argc >=1 ) return 1;
	start = argv[1];
	for(end = start; *end; end++);
	for(lpos = i = start; i < end - lhalf; i++) {
		for(j = i; j>=start && (i + 1 + (i - j) < end) && *j == *(i+1+(i-j)); j--);
		if( i-j > lhalf) {
			lhalf = i-j;
			lpos = j+1;
		};
	};
	if(lhalf) {
		*(lpos + 2*lhalf) = 0;
		printf("%s\n", lpos);
		return 0;
	} else {
		return 1;
	}
}
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 12:24 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Zatr. Samozřejmě tam má být
	if (argc <=1 ) return 1;
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 09:52 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Jo hezká složitost O(n). Mám fakt rád tyhle akademické "počítání" složitosti. A režije na vytváření toho stromu, kopírování v paměti a podobně je vosk? Teorie je to hezká, ale skutek utek. Složitost O(n) to má leda tak na papíře.
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 12:30 moira | skóre: 30 | blog: nesmysly
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Slozitost na vytvoreni stromu je take O(n), je to v tom clanku :)
Překladač ti nikdy neřekne: "budeme kamarádi"
22.11.2006 14:13 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Vážně? Jseš si tím tak jistý, že by jsi za to dal ruku do ohně? Tak se na to mrkněme pod drobnohledem. Takže v ukkonen95() se nám n krát volá funkce upDate() a canonize(). A copak to tu máme uvnitř funkce upDate()? Na dvou místech se nám tu volá funkce test_and_split() to jednou doknce uvnitř cyklu! Takže jen funkce test_and_split() je volána více než O(n). No pak tu máme další volání funkce canonize() uvnitř funkce upDate() a zase uvnitř cyklu! Funkce canonize() je opět volána vícě než O(n)! No a aby to nebylo málo, tak funkce canonize() opět obsahuje cyklus z čehož vyplývá, že ta část uvnitř cyklu se provede ještě víckrát než samotná funkce canonize(), která sama o sobě není volána O(n), ale víckrát. Takže prdlačky švagrová. Ten algoritmus není O(n) ani kdybych zavřel obě oči a praštil se palicí do hlavy. Dokonce bych ho typoval tak na O(n^3) ná základě tohoto rozboru. Když to srovnám s kódem co jsem poslal, který má nejhorší odhad (n+2)*n/8 tedy O(n^2) a to počítám opravdu ten nejhorší případ. Nesmíš taky věřit všemu co se kde píše. Ono takhle akademicky to vypadá dobře, ale když jdeš po tom algoritmu do důsledku tak se nám tam n krát zavolá cosi co má v sobě cyklus uvnitř něhož se nám zase zavolá ? krát cosik a to cosik má v sobě cyklus, která může být zavolán m krát, přičemž hodnota m je nějaká konstanta*n. Tedy přinejmenším O(n^2), ale taky možná O(n^3) protože neznám ?. Abych pravdu řek, nechce se mi po tom pátrat, ale vzhledem k tomu, že je to cosi se stromy, tak tomu dejme O(n^2*log2n) ať nežeru. O(n) fakt ani omylem.
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 14:33 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Až na to, že všechny vaše úvahy jsou jen horní odhady…
22.11.2006 15:12 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Vážně? Ve funkci ukkonen95() jsou funkce upDate() a canonize() volány vždy n krát. Uvnitř funkce upDate() je funkce test_and_split() vždy volána nejméně jednou, ale může být i více krát. Stejně tak funkce canonize() je vždy n krát volána přímo z ukkonen95() a může být volána i z upDate() a to i více než jednou. Takže tu máme dvě funkce, které mohou být volány n*a, kde a není nikdy menší než 1, ale a s velkou pravděpodobností závisí na složitosti stromu tedy asi na O(log2n). No a v samotné funkci canonize() máme cyklus, který závisí na délce subřetězce, tedy na n. Takže tvrdit o něčem takovém, že to má složitost O(n), je prostě lež jako věž. To neukecáte, ani kdyby jste se na hlavu postavil. Jen proto, že se v javě až tak nevyznám, jsem možná přehlédl ještě nějaké to kopírování v paměti zase se složitostí O(n), které nám z toho všeho pěkně udělají nejméně O(n^2) jako když vyšije. Mužete to milionkrát okecat, ale O(n) to prostě není.
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 15:19 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Nehodlám nic ukecávat, to, co jste předvedl, nemá s důkazem dolního odhadu časové složitosti nic společného a silácké výrazy typu "prdlačky švagrová" nebo "ani kdybych zavřel obě oči a praštil se palicí do hlavy" tomu nijak nepomohou. Nevidím sice na první pohled, že to je lineární, ale stejně tak bych si nedovolil na základě tak chatrných úvah, jako jsou ty vaše, rezolutně prohlášovat, že to lineární není.
22.11.2006 16:03 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Nehodlám nic ukecávat, to, co jste předvedl, nemá s důkazem dolního odhadu časové složitosti nic společného a ...
Ahá, takže ono jde o dolní odhad složitosti, tak to ten můj algoritmus má taky dolní odhad O(n). Pro řetězec neobsahující žádnou dvojici za sebou jdoucích stejných znaků se provede právě n-1 porovnání. Aha, takže proč to dělají tak složitě? Ten můj algoritmus je mnohem jednodužší a má stejný dolní odhad složitosti :-)
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
22.11.2006 16:11 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Achich ouvej. Chcete-li vyvrátit tvrzení, že univerzální horní odhad složitosti je O(n), potřebujete najít nějakou posloupnost vstupů, pro niž je dolní odhad složitosti není O(n), tj. označíme-li jejich složitosti t_n, posloupnost t_n/n není omezená. Takže chcete-li vyvrátit horní odhad (a právě o to se celou dobu snažíte), potřebujete udělat dolní odhad. Dolní odhad jste sice udělal, ale dokázal jste pouze cn, což nic nevyvrací, všechny další výroky, že je to určitě n log n a pravděpodobně n^2, jsou jen mlha, ne důkaz.
22.11.2006 15:22 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Ještě doplnění: pozorný čtenář si toho jistě všimne sám, ale pro ty méně pozorné zdůrazním, že jediné, co jste svou v tomto příspěvku úvahou skutečně dokázal, je skutečnost, že časová složitost je alespoň O(n), což není nijak v rozporu s příspěvkem, do kterého jste se tak vehementně obul…
22.11.2006 16:22 podlesh | skóre: 37 | Praha
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Pro ty méně i více pozorné bych ještě dodal, že přehození pojmů "horní" a "dolní" odhad celou tuto diskusi naprosto dorazilo. Doporučuji začít znovu.
22.11.2006 16:24 podlesh | skóre: 37 | Praha
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Aha, už vidím podrobnější vysvětlení, teď to dává smysl :-)
22.11.2006 15:12 Martin Beránek | skóre: 33 | blog: mousehouse | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
Mám fakt rád tyhle akademické "počítání" složitosti.
V tom pripade vam doporucuji toto PDF.
never use rm after eight
22.11.2006 15:24 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Hledání nejdelší symetrické části řetežce
To je všechno hezké, ale ten algoritmus nemá složitost O(n), ale větší.
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.