Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> array_temporario(string & padrao){
- vector<int> index;
- int j = 0, i;
- for(i = 1; i < padrao.length();)
- if(padrao[i] == padrao[j]){
- index.push_back(j+1);
- j++;
- i++;
- } else {
- index.push_back(0);
- i++;
- }
- return index;
- }
- int KMP(string & texto, string & padrao){
- vector<int> index = array_temporario(padrao);
- int i = 0, j = 0;
- while(i < texto.length() && j < padrao.length()){
- if(texto[i] == padrao[j]){
- i++; j++;
- } else {
- if(j != 0) j = index[j-1];
- else i++;
- }
- }
- return i-padrao.length();
- }
- int main(){
- string texto = "abcxabcdabcdabcy", padrao = "abcdabcy";
- cout << KMP(texto, padrao) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement