Pagini recente » Cod sursa (job #1640296) | Cod sursa (job #1567347) | Cod sursa (job #502719) | Cod sursa (job #2393652) | Cod sursa (job #2861424)
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
#define ll int int
// ======== Files ========
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#pragma endregion Template
vector<int> automata_prefix(string str) {
int len = str.length(), cnt = 0;
vector<int> pi(len);
for (int i = 1; i < len; i++) {
while (cnt != 0 && str[cnt + 1] != str[i])
cnt = pi[cnt - 1];
if (str[cnt + 1] == str[i])
++cnt;
pi[i] = cnt;
}
return pi;
}
vector<int> automataKMP(vector<int> patt, string pattStr, string str) {
int lenPat = pattStr.length() - 1, lenStr = str.length();
vector<int> positions;
int cnt = 0;
for (int i = 1; i < lenStr; i++) {
while (cnt != 0 && pattStr[cnt + 1] != str[i]) {
cnt = patt[cnt - 1];
}
if (pattStr[cnt + 1] == str[i])
++cnt;
if (cnt == lenPat)
positions.push_back(i - lenPat);
}
return positions;
}
void print(vector<int> toPrint) {
fout << toPrint.size() << '\n';
if (int(toPrint.size()) > 1000)
for (int i = 0; i < 1000; i++)
fout << toPrint[i] << ' ';
else
for (int i = 0; i < int(toPrint.size()); i++)
fout << toPrint[i] << ' ';
}
void solve() {
string pattern, text;
fin >> pattern >> text;
transform(pattern.begin(), pattern.end(), pattern.begin(), ::tolower);
transform(text.begin(), text.end(), text.begin(), ::tolower);
vector<int> prefixVector = automata_prefix(pattern);
vector<int> ans = automataKMP(prefixVector, pattern, text);
print(ans);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; //cin >> t;
while (t--) {
solve();
}
return 0;
}