Pagini recente » Cod sursa (job #3290536) | Cod sursa (job #902009) | Cod sursa (job #2885739) | Cod sursa (job #3290539) | Cod sursa (job #3259602)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[2000005]; // lps[0] = 0 implicit
vector<int> ans;
int val;
int main() {
string pattern, word;
fin >> pattern;
fin >> word;
int n = pattern.size(), m = word.length(), len = 0;
for(int i = 1; i < n; ) {
if(pattern[i] == pattern[len]) {
lps[i++] = ++len;
} else if(len != 0) {
// Pt a da skip peste caractere
len = lps[len - 1];
} else {
// lps[i] = 0;
++i;
}
}
// Folosesc array precalculat pt a verifica in timp liniar
for(int i = 0, j = 0; i < m; ) {
if(pattern[j] == word[i]) {
++i; ++j;
if(j == n) {
++val;
if(ans.size() < 1000) {
ans.push_back(i - j);
}
j = lps[j - 1];
}
} else if(j != 0) {
j = lps[j - 1];
} else {
++i;
}
}
fout << val << "\n";
for(int x : ans) {
fout << x << " ";
}
return 0;
}