Pagini recente » Cod sursa (job #1746540) | Cod sursa (job #764553) | Cod sursa (job #1572371) | Cod sursa (job #1861091) | Cod sursa (job #2806768)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s1, s2;
long long l1, l2, len;
vector<long long> lps, rezi;
int main() {
cin >> s1;
l1 = s1.size();
cin.get();
cin >> s2;
l2 = s2.size();
lps.emplace_back(0);
long long i = 1;
long long rez = 0;
while (i < l1) {
rez = 0;
if (s1[i] == s1[len]) {
len++;
lps.emplace_back(len);
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps.emplace_back(len);
i++;
}
}
}
i = 0;
long long j = 0, cnt = 0;
while (i < l2) {
if (s1[j] == s2[i]) {
i++;
j++;
}
if (j == l1) {
cnt++;
rezi.emplace_back(i - j);
j = lps[j - 1];
}
if (s1[j] != s2[i]) {
if (j != 0) {
j = lps[j - 1];
}
else {
i++;
}
}
}
cout << cnt<<'\n';
for (int k = 0; k < rezi.size(); k++) {
if (k < 1000) {
cout << rezi[k] << ' ';
}
}
}