Pagini recente » Monitorul de evaluare | Cod sursa (job #945426) | Monitorul de evaluare | Cod sursa (job #1249620) | Cod sursa (job #2275311)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
string target, s;
in >> target >> s;
s = target + s;
vector<int> z(s.size(), 0);
z[0] = 1;
int l = 0, r = 0, ans = 0;
vector<int> sol;
for(int i = 1; i < s.size(); i ++) {
if(s[i] > r) {
int j = 0;
while(j + i < s.size() && s[j] == s[j + i])
j ++;
r = i + j - 1;
l = r - j;
z[i] = j;
} else {
int pretender = i - l + 1;
z[i] = z[pretender];
if(z[pretender] >= (r - i + 1)) {
int j = 0;
while(j + z[pretender] + i < s.size() && s[j + z[pretender] + 1] == s[j + i + z[pretender]])
j ++;
z[i] += j;
}
if(i + z[i] - 1 > r) {
r = i + z[i] - 1;
l = i;
}
}
if(z[i] >= target.size()) {
ans ++;
if(ans <= 100)
sol.push_back(i - target.size());
}
}
out << ans << "\n";
for(auto it : sol)
out << it << " ";
return 0;
}