Pagini recente » Cod sursa (job #150203) | Cod sursa (job #765834) | Cod sursa (job #1490974) | Cod sursa (job #106796) | Cod sursa (job #2717415)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int pref[2000005], nr;
vector<int> ans;
int main() {
fin >> a >> b;
for(int i = 1; i < a.length(); i++) {
pref[i] = pref[i-1];
while(pref[i] > 0 && a[i] != a[pref[i]])
pref[i] = pref[pref[i]-1];
if(a[i] == a[pref[i]])
pref[i]++;
}
int k = 0;
for(int i = 0; i < b.length(); i++) {
while(k > 0 && a[k] != b[i])
k = pref[k-1];
if(a[k] == b[i]) k++;
if(k == a.length()) {
if(ans.size() < 1000)
ans.push_back(i-a.length()+1);
nr++;
}
}
fout << nr << '\n';
for(auto x: ans) fout << x << ' ' ;
}