Hledání v řetězci – C / C++ – Fórum – Programujte.com

Mám za úkol udělat program, který by v řetězci vyhledal jiný řetězec (slovo) a spočítal kolikrát v původním řetězci je. Porádí někdo ja číst postupně řetězec nebo jak to udělat?

Zalezi, jestli ten retezec mas v charu, nebo stringu.String ma specialni funkce na hledani.U charu si je myslim musis napsat sam.

dobře.dík. tak to budu řešit stringem. a ještě jak dostat celý text do stringu. případně do řádků?
použil jsem toto,ale tím cyklem pro opakování přijdu o první písmenko. :-(

int i=0;
while (fread(&z,sizeof(char),1,f)==1)
{
fgets(t,sizeof(t)-1,f);
fputs(t,stdout);
}


t je sring,z je char,f je soubor

Nejjednodusi to je resit pres fstream

fstream nazevstreamu("nazvsouboru")

#include <string>

#include <fstream>



using namespace std;





bool WriteString(std::fstream& out, const std::string& str)

{  //ulozi delku

   std::string::size_type len = str.length();

   out.write(reinterpret_cast<const char*>(&len),sizeof(std::string::size_type));

   if(out.bad()) return false;

   // zapise samotna data

   out.write(reinterpret_cast<const char*>(str.c_str()), sizeof(char)*len); 

   if(out.bad()) return false;

  return true;

}





bool ReadString(std::fstream& in, std::string& str) // dodelat kontroly na eof, atd..

{ std::string::size_type len = 0;

  in.read(reinterpret_cast<char*>(&len), sizeof(std::string::size_type));

  if(in.bad()) return false;

  str.clear(); // vymaze puvodni obsah

  str.reserve(len); // alokuje dostatecne mnozstvi

  in.read(&str[0], len);// tohle si muzu dovolit jen protoze vim, ze string je SEKVENCE -tedy kontejner, ktery ma prvke linearne za sebou

 if(in.bad()) return false;

 return true;

} 

To yaqwsx : chech, myslim ze to je celkem jedno, oboji je proste posloupnost znaku. to ze ma string specialni funkce na hledani, akorat znamena ze v ramci te tridy byl implementovan nejaky vyhledavaci algoritmus, ktery ovsem pracuje s posloupnosti charu v ramci onoho stringu.

To Dr.ERROR : jestli chces efektivne prohledavat text tak by ti takovehle veci asi nemely delat problem).

algoritmu na hledani v textu je nekolik. o trivialnim ani nebudu mluvit, zminim docela zajimavy Boyer-Moore, ktery se od trivialniho lisi fikanym opatrenim: porovnavas jen posledni pismeno vzoru s prohledavanym textem, v pripade shody se posouvas o jedno zpet. pred prohledavanim si udelas jednoduchou tabulku pritomnosti vsech pismen abecedy ve vzoru, a v pripade neshody posl. pismena vzoru se aktualni pozici v prohledavanem textu a zaroven absenci onoho pismena aktualni pozice v one tabulce se muzes dopredu posunout o celou delku vzoru, jinak pouze o jedna. casova narocnost tohoto algorimu je L(delka vzoru - na vytvoreni tabulky) + M(velikost prohledavaneho textu: kazde pismeno zkoumame maximalne jednou - bud od nej pujdeme vpred, tedy o cele L, nebo o jedna zpet - ovsem maximalne L-1: protoze tam uz by slovo koncilo), tedy O(L + M), je-li L male lze ho zanedbat.

dalsi efektivni je Knuth-Morris-Prat, na to abych ho zde popisoval je asi prilis slozity (pokud vas presto zajima napiste), zalozen je na tom ze v vzoru hleda suffixy ktere jsou zaroven prefixy, a podle nich zkonstruuje tabulku posunu pro kazdy znak v pripade neshody. opet mame casovou narocnost O(M+L).

idelanim resenim problemu je konstrukce vyhledavaciho automatu, ktery pracuje obdobne jako Knuth-Morris-Prat, ovsem pro libovolny pocet hledanych slov najednou. princip je v zalozeni stromu stavu, kde kazdy stav reprezentuje prefix nejakeho vzoru, a posouvanim v textu se zaroven pohybujeme po stromu. opet automat pracuje v case O(M+P), kde P je soucet L vsech vzoru. je ovsem nutno zapocitat i vypis vsech vyskytu vzoru v textu.

dale existuje algoritmus Karp-Rabin, o tom vsak mnoho povedomi nemam az na to ze je zalozeny na hashovani (coz da se rici mluvi za vse).

Neznalost standardnych funkcii je jasna pre tych co ti radili...

Na taketo veci samozrejme existuju funkcie v standarde jazyka C...

#include <string.h>

a funkcie strstr(str1, str2), ktora ti hlada str2 v str1 a strchr(str, char) ktora ti hlada znak char v retazci str ...

Akurat ze strstr s atrchr vracaju pointre, ktore ale ty vobec nepotrebujes pouzivat, takze v tom neni problem, ani ked s nimi nevies pracovat...

A este jedna vec, nevie uz presne, to musis vyskusat, ale sa mi zda, ze ked budes viac krat hladat ten isty retazec a znak v tom istom retazci, tak stale dostavas ten isty pointer, taze to zrejme bude treba osetrit takym sposobom, ze proste prepises v povodnom retazci znaky, ktore odpovedaju hladanemu znaku, alebo retazci nejakymi inaksimi znakmi, napr aj prazdnymy znakmi, teda medzerami... ' '

To Payne : IMHO: ja teda nevim, ale pokud se clovek chce naucit programovat (je rozdil mezi tim umet nejaky konkretni jazyk (jeho syntaxi) a vlastnim programatorskym myslenim), tak by vubec nebylo od veci implementovat si vlastni algoritmy a nepouzivat knihovni funkce - navic to neni zadne slozite programovani, pouze nejaka prace s poli, pointerama, apod.. Co pak, kdyz bych chtel napsat ten program v jinem jazyku? Jen muj nazor...

To Gadael,

ono takto, dotyzny nenapisal ze nemoze pouzit uz naprogramovane funkcie...

A taketo veci ma mozno zmysel programovat len ked sa clovek uci, ako algorimus je ti to na nic a taktiez je lepsie pouzivat predom uz definovane funkcie, co su jednak rokmi overene, ze pracuju spravne, a jednak su najme rychlostne optimalizovane, takze urcite budu rychlejsie ako keby si si to sam napisal...

To Gadael :

Co pak, kdyz bych chtel napsat ten program v jinem jazyku?

Děkuji Payne. Konečně odpověď pro mne. Jinač souhlasím s tím, že knihovní f-ce tu na něco jsou tak proč je nevyužít. Ale chce to čas než se v tom trošku naučím. takže díky :-)

obecne souhlasim spise s Gadaelem, knihovni funkce bych vyuzival, ale minimalne jako cviceni je lepsi si aspon nektere napsat. navic pokud se nemylim neexistuje knihovni vyhledavaci automat, takze pokud chcete vyhledavat vice slov a chcete efektivni reseni, mate s knihovnimi funkcemi smulu