Pagini recente » Cod sursa (job #131208) | Cod sursa (job #158474) | Cod sursa (job #1845706) | Cod sursa (job #501907) | Cod sursa (job #2399249)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string pattern, text;
int lps[2000004];
vector <int> ans;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin >> pattern;
cin >> text;
int len = 0;
int i = 1;
lps[0] = 0;
while(i < pattern.size())
{
if(pattern[i] == pattern[len])
{
len++;
lps[i] = len;
i++;
}
else {
if(len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
i = 0;
int j = 0;
while(i < text.size())
{
if(pattern[j] == text[i])
{
++i;
++j;
}
if(j == pattern.size())
{
ans.push_back(i - j);
j = lps[j - 1];
}
else if(i < text.size() && pattern[j] != text[i]) {
if(j) j = lps[j - 1];
else {
i++;
}
}
}
cout << ans.size() << '\n';
int cnt = 0;
for(auto x: ans) {
if(cnt == 1000) break;
cnt++;
cout << x << ' ';
}
return 0;
}