Pagini recente » Cod sursa (job #2887996) | Cod sursa (job #1070493) | Cod sursa (job #421376) | Cod sursa (job #1795653) | Cod sursa (job #2979553)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int kN = 2e6 + 5;
string a, b;
int z[kN];
int main(){
ios_base::sync_with_stdio(false);
fin >> a >> b;
b = a + "$" + b;
int n = (int)b.size();
int m = (int)a.size();
int l = 0, r = 0;
for (int i = 1; i < n; i++){
if (i <= r){
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && b[z[i]] == b[i + z[i]]){
++z[i];
}
if (i + z[i] - 1 > r){
l = i;
r = i + z[i] - 1;
}
}
vector<int>ans;
for (int i = 0; i < n; i++){
if (z[i] == m){
ans.push_back(i - m - 1);
}
}
fout << (int)ans.size() << '\n';
for (int i = 0; i < min(1000, (int)ans.size()); i++){
fout << ans[i] << ' ';
}
}