Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef busca
- #define busca
- #include "busca.h"
- #include "stdio.h"
- #include "stdlib.h"
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- using namespace std;
- //complexdade no pior caso O:(n)
- //linguagem c
- int kmp(int tam_str, int tam_substr, char* str, char* substr){
- if (tam_substr<=tam_str)
- {
- int i=0, j=0;
- while(i<tam_str){
- if (*(substr+j)==*(str+i))
- {
- j++;
- i++;
- }
- else{
- i++;
- j=0;
- }
- if (j==(tam_substr-1))
- return 1;
- }
- }
- return 0;
- }
- //======================================================================
- //complexidade pior caso O:((log2.n)+(logn.m))
- int lcs(string str, string substr){
- int j=0;
- sort(str.begin(),str.end());//log2.n
- for (int i = 0; i <= substr.size(); i++)
- {
- if (binary_search(str.begin(),str.end(),substr[i])) //logn.m
- j++;
- else
- return 0;
- if (j==substr.size())
- return 1;
- }
- return 0;
- }
- void lcs2(string str1, string str2){
- int tam;
- string menor, maior;
- sort(str1.begin(),str1.end());
- sort(str2.begin(),str2.end());
- if (str1.size()>str2.size()){
- tam=str2.size();
- menor=str2;
- maior=str1;
- }
- else{
- tam=str1.size();
- menor=str1;
- maior=str2;
- }
- for (int i = 0; i <= tam; i++)
- {
- if(binary_search(maior.begin(),maior.end(),menor[i]))
- cout<<menor[i];
- }
- cout<<endl;
- }
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement