Ubuntu Suomen keskustelualueet
Ubuntun käyttö => Ohjelmointi, palvelimet ja muu edistyneempi käyttö => Aiheen aloitti: teele - 29.01.22 - klo:10.05
-
Pitemmässä merkkijonossa on lyhyitä alimerkkijonoja, jotka haluttaisiin korvata niiden uusilla arvoilla.
aaa aa x0x1 aaa x2 a x3 aaaaaaaaaaaaaa x4 .....
Kaikki x-arvot halutaan korvata uusilla arvooilla, jotka voivat olla vaikka suoraan vektoriista [y0, y2, y3 .... ] tai muulla tavalla tunnettuja niin, että jokaista x-arvoa pitäisi tulla korvaamaan tunnettu uusi y:n arvo
aaa aa y0y1 aaa y2 a y3 aaaaaaaaaaaaaa y4 .....
Miten korvaus kannattaisi tehdä c++ :aa ja sen stl: ää käyttäen niin, että ei tekisi turhan raskasta proseduuria, O(n) tuntuisi mahdolliselta.
-
https://fi.frwiki.wiki/wiki/Algorithme_de_Knuth-Morris-Pratt
Tästä varmaankin löytyy valmiiksi pureskeltuja vastauksia (siis valmiita koodinpätkiä), mutta sen avulla tosiaan ongleman voi hoitaa kaipaamallasi O(n):llä.
Säännölliset lausekkeet löytyy monista kielistä, jotka on käsittääkseni toteutettu tällä algoritmilla.
Edit - Tällainen algoritmi löytyi C-sukuiselle kielelle, en tosin ole tarkastanut, enkä kokeillut kyseistä koodia:
https://www.geeksforgeeks.org/finite-automata-algorithm-for-pattern-searching/