Pagini recente » Cod sursa (job #2271028) | Cod sursa (job #2779375) | Cod sursa (job #1579859) | Cod sursa (job #1179685) | Cod sursa (job #2067829)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const nmax = 2000000;
string s1, s2;
int pre[5 + 2 * nmax];
void computepre() {
int i = 0;
int j = 1;
while(j < s1.size()) {
if(s1[i] == s1[j]) {
pre[j] = i + 1;
i++;
j++;
} else {
if(i == 0){
pre[j] = 0;
j++;
} else {
i = pre[i - 1];
}
}
}
}
int main() {
in >> s1 >> s2;
int initsize = s1.size();
s1 += "*" + s2;
computepre();
vector<int> sol;
int sum = 0;
for(int i = initsize + 1; i < s1.size(); i++){
if(pre[i] == initsize) {
sum++;
if(sum <= 1000)
sol.push_back(i - initsize - initsize);
}
}
out<< sum << '\n';
sum = 0;
for(int i = 0; i < sol.size(); i++) {
out << sol[i] << " ";
}
return 0;
}