Pagini recente » Cod sursa (job #2051858) | Cod sursa (job #2079722) | Cod sursa (job #2552212) | Cod sursa (job #2550846) | Cod sursa (job #2078901)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = (2000000 + 100) * 2;
string s1, s2;
int pre[1 + NMAX];
int nsol;
vector < int > sol;
void computepre(string s) {
int i = 0; //i e la sfarsitul prefizului
int j = 1; //j e la sfrasitul sufixului
pre[0] = 0;
while(j < s.size()) {
if(s[i] == s[j]) {
pre[j] = i + 1;
i++;
j++;
} else {
if(0 < i)
i = pre[i - 1];
else {
pre[j] = 0;
j++;
}
}
}
}
int main() {
in >> s1 >> s2;
computepre(s1 + '*' + s2);
for(int i=s1.size(); i < s1.size() + s2.size() + 1; i++) {
if(pre[i] == s1.size()) {
//cout << i - 1 - 2 * s1.size();
nsol++;
if(nsol <= 1000) {
sol.push_back(i - 2 * s1.size());
}
}
}
out << nsol << '\n';
for(int i = 0; i < sol.size(); i++)
out << sol[i] << ' ';
in.close();
out.close();
return 0;
}