Pagini recente » Cod sursa (job #575326) | Cod sursa (job #1272420) | Cod sursa (job #742377) | Cod sursa (job #983557) | Cod sursa (job #2902204)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int NMAX = 2e6;
int z[2 * NMAX + 1];
string s;
void zAlgorithm() {
int l, r;
l = r = 0;
for(int i = 1; i < s.size(); i++) {
if(i > r) {
l = r = i;
while(r < s.size() && s[r - l] == s[r])
r++;
r--;
z[i] = r - l + 1;
} else if(z[i - l] < r - i + 1) {
z[i] = z[i - l];
} else {
l = i;
while(r < s.size() && s[r - l] == s[r])
r++;
r--;
z[i] = r - l + 1;
}
}
}
string a, b;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ans[NMAX];
int main() {
fin >> a >> b;
s = a + '%' + b;
zAlgorithm();
int x = 0;
for(int i = 1; i < s.size(); i++) {
if(z[i] == a.size()) {
ans[x++] = i - (int)a.size() - 1;
}
}
fout << x << endl;
for(int i = 0; i < x; i++)
fout << ans[i] << ' ';
fin.close();
fout.close();
return 0;
}