Pagini recente » Cod sursa (job #3260975) | Cod sursa (job #69348) | Cod sursa (job #1179712) | Cod sursa (job #19409) | Cod sursa (job #2430928)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int* generateLps(string str) {
int *lps = new int[str.length()];
lps[0] = 0;
int i = 1; // Current index in string
int length = 0; // Curent length of prefix
int N = str.length(); // Length of the string
// String is not done
while (i < N) {
// Match betwen curent position and coresponding prefix position
if (str[length] == str[i]) {
length++;
lps[i] = length;
i++;
} else {
// if we have already checked for length == 0 we increment index
if (length == 0) {
lps[i] = 0;
i++;
} else {
// This will take us to the first character after the prefix
// So we can check if the current char may be put here
length = lps[length];
}
}
}
return lps;
}
void kmp(string str1, string str2, int* lps, ofstream& out) {
int result[1000];
int size = 0;
int i = 0; // index in str1
int j = 0; // index in str2
while (j < (int)str2.length()) {
if (size == 1000) {
break;
}
if (str2[j] == str1[i]) {
i++;
j++;
if (i == (int)str1.length()) {
result[size] = j - i;
size++;
i = lps[i - 1];
}
} else {
// Verified with the first letter of str1
if (i == 0) {
j++;
} else {
i = lps[i - 1];
}
}
}
out << size << endl;
for (int i = 0 ; i < size ; ++i) {
out << result[i] << " ";
}
}
int main() {
ifstream in;
in.open("strmatch.in");
ofstream out;
out.open("strmatch.out");
if (!in || !out) {
std::cout << "Problem with opening files!\n";
return -1;
}
string str1, str2;
in >> str1 >> str2;
int *arr = generateLps(str1);
kmp(str1, str2, arr, out);
delete[] arr;
return 0;
}