Pagini recente » Cod sursa (job #1399163) | Cod sursa (job #1721541) | Cod sursa (job #1410703) | Cod sursa (job #1627371) | Cod sursa (job #2765270)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main() {
string s1, s2;
f >> s2 >> s1;
int n1 = s1.length(), n2 = s2.length();
int table[n2] = {0};
table[0] = -1;
int maxLength = 1;
for (int i = 1; i < n2; i++) {
if (table[i-1] > -1 && s2[i] == s2[table[i-1] + 1]) {
table[i] = table[i-1] + 1;
maxLength = maxLength > table[i] ? maxLength : table[i];
} else if (s2[i] == s2[0]) {
table[i] = 0;
} else {
table[i] = -1;
}
}
int i = 0, j = -1, count = 0;
vector<int> results;
// for (int i = 0; i < n2; i++)
// cout << table[i] << " ";
// cout << "\n";
while (i < n1) {
//cout << i << " - i : j - " << j << "\n";
if (j == n2 - 1) {
if (results.size() < 1000)
results.push_back(i - j - 1);
count++;
j = -1;
i -= (maxLength + 1);
} else {
if (s1[i] == s2[j+1]) {
i++;
j++;
} else if (j > -1) {
j = table[j];
} else {
i++;
}
}
}
if (j == n2 - 1) {
if (results.size() < 1000)
results.push_back(i - j - 1);
count++;
}
g << count << "\n";
for (int i = 0; i < results.size(); i++)
g << results[i] << " ";
return 0;
}