Pagini recente » Cod sursa (job #2719431) | Cod sursa (job #1025332) | Cod sursa (job #353625) | Cod sursa (job #1466168) | Cod sursa (job #2978959)
#include <bits/stdc++.h>
#define MAX 2000000
#define FILES freopen("strmatch.in","r",stdin);\
freopen("strmatch.out","w",stdout);
using namespace std;
int lps[MAX + 5];
string a, b;
vector<int> ans;
int main()
{
FILES
cin >> a;
int i = 0, j = 1;
while(j < a.size())
{
while(i > 0 && a[j] != a[i])
i = lps[i - 1];
if(a[i] == a[j])
lps[j] = i + 1, i++;
j++;
}
cin >> b;
j = 0;
for(int i = 0;i < b.size(); ++i)
{
while(j > 0 && b[i] != a[j])
j = lps[j - 1];
if(b[i] == a[j])
j++;
if(j == a.size()){
ans.push_back(i - j);
j = lps[j - 1];
}
}
std::cout << ans.size() << '\n';
for(int i = 0;i < min((int)(ans.size()), 1000); ++i)
std::cout << ans[i] + 1 << ' ';
}