Pagini recente » Cod sursa (job #2129318) | Cod sursa (job #1197532) | Cod sursa (job #2537232) | Cod sursa (job #2455701) | Cod sursa (job #2899182)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int lps[2000005], l = 0;
vector < int > v;
void compute_lps(string a) {
int len = 0, i = 1, n = a.size();
while(i < n) {
if (a[i] == a[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
void kmp(string a, string b) {
int i = 0, j = 0, n = a.size(), m = b.size();
while(i < n) {
if (a[i] == b[j]) {
i++, j++;
}
if (j == m) {
l++;
if(v.size() < 1000) v.push_back(i - j);
j = lps[j - 1];
}
else if (i < n && a[i] != b[j]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}
int main() {
string s, pat;
in >> pat >> s;
compute_lps(pat);
kmp(s, pat);
out << l << "\n";
for (auto it : v) out << it << " ";
return 0;
}