Hľadanie podreťazca v reťazci [C]

Ahojte, robím program v C-čku, a potrebujem dosiahnuť, aby som v sekvencii znakov, načítanej v jednorozmernom poli našiel pod-sekvenciu, a vypísal ju. Sekvencia už je v poli načítaná. Podsekvenciu by som si mal zvoliť zo vstupu.

Čiže, napríklad, sekvencia:
ADFGKDWNIDFGMDIKDWOMFGMDWFG

Podsekvencia:
FG

Nájde všetky podsekvencie "FG" a vypíše ich spolu s poradovým číslom znaku a troma znakmi pred a za touto sekvenciou. Ak sa pred ňou alebo za ňou nenachádza potrebný počet znakov, budú nahradené pomlčkou.

V tomto prípade by bol výstup:

3 -ADFGKDW
11 NIDFGMDI
21 WOMFGMDW
26 MDWFG---

Nechcem od vás celý kód, chcem len pomoc, pretože som sa dosť zasekol. Ešte by som podotkol, ideálne by bolo vyhnúť sa stringom (ak je to možné). V najhoršom prípade by to nevadilo.

Ďakujem za pomoc.

BX · Príspevok od používateľa BX » 24 nov 2013, 16:02

A máš napísať algoritmus, alebo to len použiť? Len sa uisťujem, či náhodou nehľadáš funkciu strstr http://www.cplusplus.com/reference/cstring/strstr/

O strstr som počul, ide o to, že je to semestrálny projekt do školy, a Stringy sme ešte nemali, teda by som sa im rád vyhol. Potreboval by som to napísať nejak mechanickejšie.

metthal

http://en.wikipedia.org/wiki/Knuth%E2%8 ... _algorithm alebo http://en.wikipedia.org/wiki/Boyer%E2%8 ... _algorithm

ak to ma byt trocha viac efektivne, aj ked neviem ze ci strstr neimplementuje BM s nejakou heuristikou.

EDIT: Ak sa jedna o strednu skolu tak postaci naivny algoritmus staleho prehladavania retazca znak po znaku a pri nejakej odlisnosti sa proste posunut na dalsi znak.

Jedná sa o vysokú školu, ale myslím, že ide len o to aby program fungoval. O efektivitu mi nejak nejde. Algoritmi, ktoré si postol sa mi zdajú možno zbytočne zložité, či nie?

BX · Príspevok od používateľa BX » 24 nov 2013, 16:23

Záleží na tom, čo sa vyžaduje a ako veľmi hnusné vstupy to má zvládať. Napríklad ak budem vyhľadávať v reťazci FFFFFFFF a hľadať mám podreťazec FFF, koľko krát tam je? Jednoduché, hlúpe algoritmy povedia, že dva krát. Tie zložitejšie povedia 6.

Hľadáš v jednorozmernom poli, v ktorom sú zapísané iba znaky A,C,G,T. Podsekvencia má mať dĺžku maximálne 5 znakov.

BX · Príspevok od používateľa BX » 24 nov 2013, 16:34

To na tom nič nemení, stále môžeš vyhľadávať AAA v samych Ačkach. No každopádne, tak to skús implementovať jednoducho a postupne to vylepšuj, ak to bude treba. Napíš algoritmus, ktorý príde na prvý znak a vyskúša tie ďalšie, či je tam substring. Ak nie, prejde na ďalší znak a znovu vyskúša tie ďalšie, či je to ono. Ak áno, vypíš, čo je treba a posuň sa na ďalší znak (zase len o jeden).
To by podľa mňa malo aj stačiť, takýto algoritmus je dostatočne rýchly pre malé dĺžky substringu (a to je u teba max 5)

Porovnať dva stringy určite vieš (znak po znaku v cykle). Viac ti tam toho netreba.

Ja som z toho jeleň. Už štyri krát som zmazal nejaké pokusy o kód, vždy som sa zasekol niekde pri začiatku.

Navyše som zistil, že by som to teda mal robiť bez tých stringov, čiže iba s jednorozmernými poľami.
Nevedel by mi niekto postnúť nejaký pár-riadkový mechanizmus (načítanie 1-5 znakov do poľa, porovnávanie s vopred načítaným poľom (sekvenciou), aby som to pochopil?). Tausend dank. Z tých samotných cyklov by som sa už vysomáril, ide mi len o pochopenie mechanizmu a kostry programu - a samozrejme to načítanie neznámeho počtu znakov (1 až 5) do poľa.

BX · Príspevok od používateľa BX » 24 nov 2013, 17:35

Ty už zabudni na slová string a pole

Pochop, string v C-čku je len (jednorozmerné) pole znakov, takže furt hovoríš o tom istom. Neviem, čo vám zakazujú používať, asi funkcie zo string.h, ale to je fuk, vystačíš si aj bez nich.
Takže takto nejako by to mohlo vyzerať, na začiatok:

Kód: Vybrať všetko

#include <stdio.h> // funkcie na citanie zo vstupu

int main()
{
    char hlavny[256]; // pole max 255 znakov, tu nacitam hlavny string
    char sub[6]; // pole max 5 znakov, tu nacitam hladany substring

    gets( hlavny );
    gets( sub );

    // mam nacitane co potrebujem, idem na to
}

Mysli hlavne na to, že na konci každého reťazca máš nulový byte (proste číslo 0, podľa ktorého vieš, že je koniec stringu) To využi, nepotrebuješ tak ani dĺžku jednotlivých stringov (pretože vždy na konci vieš, že si na konci)

pcsiete

Najjednoduchší kód čo ma v tejto chvíli napadol:

Kód: Vybrať všetko

int podretazec(char * str1, char*subs) {
   int i;
	char * start = str1;
	while(*str1) {
		for(i = 0;str1[i]==subs[i] && !subs[i];i++) 
			;
		if(subs[i])
			return (int)(str1 - start);
		str1++;
	}
	return -1;
}

Spravil som to vyslovene primitívne, mechanicky, ale program po zadaní subsekvencie nerobí nič. Viete mi poradiť?

http://pastebin.com/a0gVADc2

Ako by to malo fungovať:
k1 - poradie prvku v hlavnej sekvencii
k2 - poradie prvku v subsekvencii
pocet - počet rovnakých znakov v hlavnej a sub sekvencii idúcich po sebe

ak sa k1 rovná k2, počet sa zvýši, a preskočí sa na ďalší znak. Ak sa rovná aj ten, proces sa opakuje. V inom prípade sa počet aj k2 vynulujú. k1 ale ostáva, pretože v hlavnom cykle sa pokračuje. Ak sa "pocet" rovná "i", a teda počtu zapísaných znakov v subsekvencii, tak sa našla podobnosť a program ju vypíše štýlom, aký som spomínal nižšie. (Po tomto vypísaní by sa tam malo nachádzať ešte podobné vynulovanie k2 a pocet-u).

EDIT: Ja ch*j som zabudol zapísať hodnoty do poľa. Už to niečo robí, ale nie celkom tak, ako by malo. Pri tejto sekvencii:
AACGTACGTAACGaatt

a zadaní podsekvencie "AC" to vypíše toto:
AC
65 A A C G T Ŕ
67 A A C G T A Ŕ

a ďalej už nejde zadávať nič do vstupu.

pcsiete

Hensym napísal:Spravil som to vyslovene primitívne, mechanicky, ale program po zadaní subsekvencie nerobí nič. Viete mi poradiť?

http://pastebin.com/a0gVADc2

Ako by to malo fungovať:
k1 - poradie prvku v hlavnej sekvencii
k2 - poradie prvku v subsekvencii
pocet - počet rovnakých znakov v hlavnej a sub sekvencii idúcich po sebe

Čo je to "prvok"? Na čo presne slúži "pocet"?

a ďalej už nejde zadávať nič do vstupu.

Niet nad debugovanie. Pozri si ako presne program beží a kde to stojí.

Prvok je písmeno v poli, a "pocet" udáva počet zhôd idúcich po sebe. Teda:

Sekvencia: ABCDEFGH
Subsekvencia: ABC

pocet je 0
k1 aj k2 sú 0

Keďže nulté prvky v poliach sa rovnajú, zvýši sa pocet, k1 aj k2.
Keďže prvé prvky sa opäť rovnajú, zvýši sa pocet,k1 aj k2 na hodnotu 2.
Keďže aj druhé prvky sa rovnajú, k1,k2 aj pocet budú mať hodnotu 3.

A keďže 3 je aj hodnota "i", teda počet znakov v subsekvencii, už je subsekvencia považovaná za kompletnp, vypíše sa, a "pocet" aj "k2" sa vynulujú. "k1" ale ostane, keďže v hlavnej sekvencii nechceme ísť odznova, ale pokračovať.

pcsiete

Robíš to moc komplikovane. V skutočnosti potrebuješ len k1 a i, ktoré sa bude pripočítavať ku k1 resp. začiatku podreťazca a potom bude teda stačiť už len nulovať i. Pozri sa na kód čo som tu dal predtým.

Hľadal som tam nejaké súvislosti, ale stratil som sa v tých reťazcoch. Nakoniec pracujem iba s poľami, a viem, že tým BX-a na*ieram (

), ale máme pracovať iba s tým, s čím sme zatiaľ robili, inak znížené body. Čiže ani pointre, ani reťazce. Iba riadiace štruktúry, jednorozmerné polia, atď.

Určite je x-spôsobov ako zjednodušiť ten môj bordelatý program, ktorý som postol vyššiel, no v prvom rade ho chcem spojazdniť, až potom ho budem okresávať. Tak to robím vždy.

Grasel

Hensym napísal:Hľadal som tam nejaké súvislosti, ale stratil som sa v tých reťazcoch. Nakoniec pracujem iba s poľami, a viem, že tým BX-a na*ieram ( ), ale máme pracovať iba s tým, s čím sme zatiaľ robili, inak znížené body. Čiže ani pointre, ani reťazce. Iba riadiace štruktúry, jednorozmerné polia, atď.

1. pole ukončené '\0' == C-éčkový reťazec (alebo string), teda

Kód: Vybrať všetko

int pole[4]; // hovoríme o poli intov
char policko[10]; // hovoríme o poli charov
char nazovPola[30]; char[29] = '\0'; // hovoríme o C stringu

2. pole[x] == *(pole + x), takže pole je len jednoduchší zápis ako sa dostať k určitému prvku odsadenému x miest od adresy použitím pointrov

Okrem toho, BX ti to už aj raz písal:

Pochop, string v C-čku je len (jednorozmerné) pole znakov, takže furt hovoríš o tom istom.

To je ale úplne jedno, ako som už napísal:

"...máme pracovať iba s tým, s čím sme zatiaľ robili, inak znížené body."

Teda pcsiete-ho kód môžem vylúčiť.

http://pastebin.com/Xb8xZ106 Momentálne pracujem s týmto kódom, no tu som sa zasekol.

Základná sekvencia je: AACGTGCCACGGTA

Program by mal vypísať po zadaní "AC" toto:

Kód: Vybrať všetko

2 - - A C G T G
9 G C C A C G G T

Ale miesto toho vypisuje toto:

Kód: Vybrať všetko

1 (medzera) (medzera) A A C G T ś

Samozrejme, pomlčky miesto medzier som zatiaľ nedefinoval. Musím to odovzdať dnes do šiestej, takže mi to ponáhľa.

//autoeditácia príspevku (26 Nov 2013, 15:04)
Kód som trošku vylepšil a už to v základe funguje, avšak neviem prečo, iba s niektorými písmennými kombináciami, vôbec v tom nevidím súvislosti. Napríklad z nižšie uvedených funguje iba "AC" a "ACA". (Viď. prílohu). Pridávam aj kód.

http://pastebin.com/GY8DxPVU

EDIT: Funguje to iba, keď podsekvenciu začnete písať od prvého písmena v hlavnej sekvencii. Neviete prečo?
EDIT2: Ide

chýbalo "k1++;" v else.

Hľadanie podreťazca v reťazci [C]

Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]

Re: Hľadanie podreťazca v reťazci [C]