Pagini recente » Borderou de evaluare (job #1105613) | Cod sursa (job #2737122)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
fin >> s >> t;
int szS = s.length();
s = s + "$" + t;
vector <int> z(s.length(), 0);
for (int i = 1, left = 0, right = 0; i < s.length(); ++i) {
if (i > right) {
left = right = i;
while (right < s.length() && s[right] == s[right - left])
++right;
z[i] = right - left;
--right;
}
else {
if (i + z[i - left] + 1 < right) {
z[i] = z[i - left];
}
else {
left = i;
while (right < s.length() && s[right] == s[right - left])
++right;
z[i] = right - left;
--right;
}
}
}
int cnt = 0;
vector <int> answer;
for (int i = szS; i < s.length(); ++i) {
if (z[i] == szS) {
++cnt;
if (answer.size() < 1000) {
answer.push_back(i - szS - 1);
}
}
}
fout << cnt << "\n";
for (auto& i : answer)
fout << i << " ";
fin.close();
fout.close();
return 0;
}