Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #ifndef busca
  2. #define busca
  3. #include "busca.h"
  4. #include "stdio.h"
  5. #include "stdlib.h"
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <string>
  10. using namespace std;
  11.  
  12. //complexdade no pior caso O:(n)
  13. //linguagem c
  14. int kmp(int tam_str, int tam_substr, char* str, char* substr){
  15. if (tam_substr<=tam_str)
  16. {
  17. int i=0, j=0;
  18. while(i<tam_str){
  19. if (*(substr+j)==*(str+i))
  20. {
  21. j++;
  22. i++;
  23. }
  24. else{
  25. i++;
  26. j=0;
  27. }
  28. if (j==(tam_substr-1))
  29. return 1;
  30. }
  31. }
  32. return 0;
  33. }
  34. //======================================================================
  35. //complexidade pior caso O:((log2.n)+(logn.m))
  36. int lcs(string str, string substr){
  37. int j=0;
  38. sort(str.begin(),str.end());//log2.n
  39. for (int i = 0; i <= substr.size(); i++)
  40. {
  41. if (binary_search(str.begin(),str.end(),substr[i])) //logn.m
  42. j++;
  43. else
  44. return 0;
  45. if (j==substr.size())
  46. return 1;
  47. }
  48. return 0;
  49. }
  50. void lcs2(string str1, string str2){
  51. int tam;
  52. string menor, maior;
  53. sort(str1.begin(),str1.end());
  54. sort(str2.begin(),str2.end());
  55. if (str1.size()>str2.size()){
  56. tam=str2.size();
  57. menor=str2;
  58. maior=str1;
  59. }
  60. else{
  61. tam=str1.size();
  62. menor=str1;
  63. maior=str2;
  64. }
  65. for (int i = 0; i <= tam; i++)
  66. {
  67. if(binary_search(maior.begin(),maior.end(),menor[i]))
  68. cout<<menor[i];
  69. }
  70. cout<<endl;
  71. }
  72. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement