Pagini recente » Cod sursa (job #2511199) | Cod sursa (job #2817309) | Cod sursa (job #79180) | Cod sursa (job #1286897) | Cod sursa (job #3139463)
#include <fstream>
#include<string>
#include<vector>
using namespace std;
vector<int> res;
int length = 0;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void solve(string s1, string s2) {
int l1 = s1.length(), l2 = s2.length();
vector<int> lps = vector<int>(l2, 0);
int i, j, prevLps = 0;
i = 1;
while (i < l2) {
if (s2[prevLps] == s2[i]) {
lps[i] = prevLps + 1;
prevLps++;
i++;
}
else if (prevLps == 0) {
lps[i] = 0;
i++;
}
else {
prevLps = lps[prevLps - 1];
}
}
i = 0;
j = 0;
while (i < l1) {
if (s1[i] == s2[j]) {
i++;
j++;
}
else if (j == 0) {
i++;
}
else {
j = lps[j - 1];
}
if (j == l2) {
j--;
i -= l2;
length++;
res.push_back(i);
if (length == 1000)
return;
i++;
}
}
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
solve(s2, s1);
cout << length << "\n";
for (auto nr : res) {
cout << nr << " ";
}
return 0;
}