Pagini recente » Cod sursa (job #529810) | Cod sursa (job #423198) | Cod sursa (job #2919454) | Cod sursa (job #1872430) | Cod sursa (job #1814475)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax = 2e6 + 5;
int A[NMax];
int main() {
ios::sync_with_stdio(false);
fin.tie(NULL);
string a, b;
fin >> a >> b;
a = '$' + a;
b = '$' + b;
A[1] = 0;
int k = 0;
for(int i = 2; i <= a.size(); i++) {
while(k > 0 && a[k + 1] != a[i]) {
k = A[k];
}
if(a[k + 1] == a[i]) {
k++;
}
A[i] = k;
}
k = 0;
int p = 0;
vector < int > ans;
for(int i = 1; i <= b.size(); i++) {
while(k > 0 && b[i] != a[k + 1]) {
k = A[k];
}
if(b[i] == a[k + 1]) {
k++;
}
if(k == a.size() - 1) {
p++;
if((int)(ans.size()) < 1000) ans.push_back(i - k);
k = A[k];
}
}
fout << p << "\n";
for(auto it: ans) fout << it << " ";
return 0;
}