Pagini recente » Cod sursa (job #236504) | Cod sursa (job #2777025) | Cod sursa (job #2983849) | Cod sursa (job #477045) | Cod sursa (job #2849589)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int maxN = 4e6 + 5;
int z[maxN];
void z_function (string s) {
int l = 0, r = 0;
int n = s.size();
for(int i = 1; i < n; ++i) {
if(i <= r)
z[i] = min (r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if(i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
}
int main() {
string a; fin >> a;
string b; fin >> b;
string s = a + '&' + b;
z_function(s);
vector <int> ans;
int cnt = 0;
for(int i = a.size()+1; i < s.size() && cnt < 1000; ++i) {
if(z[i] == a.size()) {
ans.push_back(i-a.size()-1);
cnt += 1;
}
}
fout << ans.size() << "\n";
for(int i = 0; i < ans.size(); ++i)
fout << ans[i] << " ";
return 0;
}