Pagini recente » Cod sursa (job #626035) | Cod sursa (job #481945) | Cod sursa (job #507198) | Cod sursa (job #2061155) | Cod sursa (job #2763917)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> make_pattern(string s) {
vector<int> v(1, 0);
int i = 0, j = 1, match_size = 0;
while (j < s.size()) {
if (s[i] == s[j]) {
i++;
j++;
match_size++;
v.push_back(match_size);
continue;
} else {
i = v[i - 1];
j++;
match_size = i;
v.push_back(match_size);
continue;
}
}
return v;
}
void solve(string pattern, string text) {
vector<int> vp = make_pattern(pattern), ans{};
int i_text = 0, i_pattern = 0, current_len = 0;
for (; i_text != text.size();) {
if (pattern[i_pattern] == text[i_text]) {
current_len++;
i_pattern++;
i_text++;
} else {
if (i_pattern == 0)
i_pattern = vp[0];
else
i_pattern = vp[i_pattern - 1];
current_len = i_pattern;
if (current_len != 0)
i_text--;
i_text++;
}
if (i_pattern == pattern.size()) {
ans.push_back(i_text - pattern.size());
i_pattern = vp[i_pattern - 1];
current_len = i_pattern;
if(ans.size()==1000)
goto label;
}
}
label:
fout << ans.size() << '\n';
for (auto it:ans)
fout << it << " ";;
}
int main() {
string a, b;
fin >> a >> b;
solve(a, b);
return 0;
}