Pagini recente » Cod sursa (job #2754363) | Cod sursa (job #1761198) | Cod sursa (job #2521015) | Cod sursa (job #2771096) | Cod sursa (job #1741155)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int Z[2*2000003];
void ZF(string s) {
int left = 0;
int right = 0;
for(int k = 0; k < s.size(); k++) {
if(k > right) {
left = k;
right = k;
while(right < s.size() && s[right] == s[right-left])
right++;
Z[k] = right-left;
right--;
} else {
int p = k+Z[k-left];
if(p <= right)
Z[k] = Z[p];
else {
left = k;
while(right < s.size() && s[right] == s[right-left])
right++;
Z[k] = right-left;
right--;
}
}
}
}
int main() {
string s1,s2,rez;
in >> s1 >> s2;
rez = s1 + "$" + s2;
ZF(rez);
int K = 0;
int am = 0;
for(int i = 0; i < rez.size(); i++) {
if(Z[i] == s1.size())
am++;
}
out << am << '\n';
for(int i = 0; i < rez.size(); i++) {
if(Z[i] == s1.size()) {
if(++K > 1000)
break;
out << i-s1.size()-1 << " ";
}
}
return 0;
}