Pagini recente » Cod sursa (job #1586204) | Cod sursa (job #1588060) | Cod sursa (job #2935025) | Cod sursa (job #2343372) | Cod sursa (job #2930108)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define MAX 2000000
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define FILES freopen("strmatch.in","r",stdin);\
freopen("strmatch.out","w",stdout);
using namespace std;
string path, str;
int lps[MAX + 5];
vector<int> ans;
int main()
{
fastio
FILES
cin >> path >> str;
int i = 0;
lps[0] = 0;
for(int j = 1;j < path.size(); ++j)
{
while(i && path[i] != path[j])
i = lps[i-1];
if(path[i] == path[j])
lps[j] = i + 1, i++;
else lps[j] = 0;
}
int j = 0;
for(int i = 0;i < str.size(); ++i)
{
while(j && str[i] != path[j])
j = lps[j-1];
if(path[j] == str[i])
j++;
if(j == path.size())
j = lps[j-1], ans.push_back(i + 1);
}
cout << ans.size() << '\n';
for(auto i : ans)
cout << i - path.size() << ' ';
}