Advertisement
neTzaolini

Najduzi substring zadatak - programiranje c++

May 22nd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.01 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void Unos(char *& string)
  5. //unos stringova
  6. {
  7. char buffer[255];
  8. cin.getline(buffer, 255);
  9. int vel = strlen(buffer) + 1;
  10. string = new char[vel];
  11. strcpy_s(string, vel, buffer);
  12. }
  13. void Dealociraj(char ** svi, int trenutno)
  14. {
  15. for (int i = 0;i < trenutno;i++)
  16. {
  17. delete[] svi[i];
  18. }
  19. delete[]svi;
  20. svi = nullptr;
  21. }
  22. bool strstr2(char ** svi, int max,char * znak)
  23. //slicno na principu funkcije strzachr u zelji da manje opteretim funkciju duzina najveceg uveo sam ovu funkciju koja ce provjeravati da li trenutni
  24. //sadrzaj buffera posjeduju svi stringovi
  25. {
  26.  
  27. bool ima = false;
  28. for (int i = 0;i < max;i++)
  29. {
  30. if (svi[i] != '\0' && strlen(znak)<strlen(svi[i]))
  31. {
  32. if (strstr(svi[i], znak) != nullptr)
  33. ima = true;
  34.  
  35. else
  36. {
  37. ima = false;
  38. break;
  39. }
  40. }
  41. }
  42. return ima;
  43. }
  44. bool strzachr(char ** svi, int max, char znak)
  45. //za manje opterecivanje funkcije duzina najveceg kako ne bi uvodio jos jednu for petlju bespotrebno uvedena je ova funkcija,provjerava da li postoji
  46. //znak u svim stringovima
  47. {
  48. bool ima = false;
  49. for (int i = 0;i < max;i++)
  50. {
  51. if (strchr(svi[i],znak) != nullptr)
  52. ima = true;
  53. else
  54. {
  55. ima = false;
  56. break;
  57. }
  58. }
  59. return ima;
  60. }
  61. char * vratijedankarakter(char znak)
  62. //kod slucajeva kada pronadje samo jedno slovo funkcija strcpy_s u funkciji unesisub nije bas pozitivno nastrojena prema jednom karakteru pa je bilo
  63. //neophodno pronaci nacin za kreiranje niza od jednog karaktera s obzirom da nisam zelio napraviti jos jedan overload funkcije unesisub jer je bilo bespotrebno
  64. //tako da sam s ovom funkcijom rijesio problem.Svakako sam probao preko template<typename T> pa da razlikujem niz karaktera i karakter jedan
  65. //ali jos uvijek se strcpy_s bunio pa sam odustao od tog rjesenja
  66. {
  67. char * buffer = new char[1 + 1];
  68. buffer[0] = znak;
  69. buffer[1] = '\0';
  70. return buffer;
  71. }
  72. char ** unesisub(char * unos,int trenutno,char ** svi)
  73. //sluzi za pohranjivanje substringova zbog kasnije pretrage mada je mozda bilo moguce dodati neki parametar u glavnoj funkciji duzinanajveceg
  74. //koji bi odma izracunavao duzinu i uporedjivao sa prethodnim substringovima ali ja sam ovako implementirao
  75. {
  76. int vel = 0;
  77. char ** temp = new char *[trenutno + 1];
  78. for (int i = 0;i < trenutno;i++)
  79. {
  80. temp[i] = new char[strlen(svi[i]) + 1];
  81. strcpy_s(temp[i], strlen(svi[i]) + 1, svi[i]);
  82. delete[] svi[i];
  83. }
  84. vel = strlen(unos);
  85. temp[trenutno] = new char[vel + 1];
  86. strcpy_s(temp[trenutno], vel+1,(unos));
  87. delete[]svi;
  88. svi = temp;
  89. return temp;
  90.  
  91. }
  92. int nadjiduzinu(char ** subovi, int trenutnosubova)//pronalazak duzine najduzeg substringa
  93. {
  94. size_t max = strlen(subovi[0]);
  95. for (int i = 1;i < trenutnosubova;i++)
  96. {
  97. if (strlen(subovi[i]) > max)
  98. max = strlen(subovi[i]);
  99. }
  100. return max;
  101. }
  102. int nadjipoziciju(char ** subovi, int trenutnosubova)//sluzi za nalazenje pozicije najduzeg stringa s obzirom da on ima najvise slova za pretragu
  103. {
  104. size_t max = strlen(subovi[0]);
  105. int pozicja = 0;
  106. for (int i = 1;i < trenutnosubova;i++)
  107. {
  108. if (strlen(subovi[i]) > max)
  109. {
  110. max = strlen(subovi[i]);
  111. pozicja = i;
  112. }
  113. }
  114. return pozicja;
  115. }
  116. int duzinanajveceg(char ** stringovi, int max)
  117. {
  118. int pozicijanajduzeg = nadjipoziciju(stringovi, max);
  119. int brojacsubova = 0;
  120. char ** subovi = nullptr;
  121. char * karakter = nullptr;
  122. for (size_t j = 0;j < strlen(stringovi[pozicijanajduzeg]);j++)
  123. if (strzachr(stringovi, max, stringovi[pozicijanajduzeg][j]))
  124. {
  125. bool dalje = true;
  126. karakter = vratijedankarakter(stringovi[pozicijanajduzeg][j]);
  127. subovi = unesisub(karakter, brojacsubova++, subovi);
  128. int brojackaraktera = 1;
  129. while (dalje)
  130. {
  131. dalje = false;
  132. brojackaraktera++;
  133. char * buffer = new char[brojackaraktera + 1];
  134. for (int k = 0;k < brojackaraktera;k++)
  135. {
  136. if (stringovi[pozicijanajduzeg][j + k] != '\0')
  137. {
  138. buffer[k] = stringovi[pozicijanajduzeg][j + k];
  139. }
  140. else
  141. break;
  142. }
  143. buffer[brojackaraktera] = '\0';
  144. if (strstr2(stringovi, max, buffer))
  145. {
  146. subovi = unesisub(buffer, brojacsubova++, subovi);
  147. delete[]buffer;
  148. dalje = true;
  149. }
  150. else
  151. {
  152. delete[] buffer; dalje = false;
  153. }
  154.  
  155. }
  156. }
  157. if (brojacsubova == 0)
  158. return 0;
  159. int velicina = nadjiduzinu(subovi, brojacsubova);
  160. Dealociraj(subovi, brojacsubova);
  161. return velicina;
  162. }
  163.  
  164. int main()
  165. {
  166. char nastavak;
  167. do {
  168. int izbor = 0;
  169.  
  170. do {
  171. cout << "Unesite broj stringova " << endl;
  172. cin >> izbor;
  173. } while (izbor < 1);
  174. cin.ignore();
  175. char ** stringovi = new char *[izbor];
  176. for (int i = 0;i < izbor;i++)
  177. {
  178. cout << i + 1 << ". string -> ";
  179. Unos(stringovi[i]);
  180. }
  181.  
  182. cout << "duzina najveceg substringa je -> " << duzinanajveceg(stringovi, izbor);
  183. cout << endl << endl << endl << endl <<"ponovo ? (y/n)" << endl;
  184. cin >> nastavak;
  185. Dealociraj(stringovi, izbor);
  186. system("cls");
  187. } while (nastavak != 'n');
  188. cout << "hvala na testiranju :)" << endl;
  189.  
  190. system("pause>0");
  191. return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement