Pagini recente » Cod sursa (job #572847) | Cod sursa (job #2366417) | Cod sursa (job #2789818) | Cod sursa (job #1170458) | Cod sursa (job #2839126)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const NMAX = 2e6;
int dp[1 + NMAX];
string s;
vector <int> sol;
void solve(int ssol){
int ans = 0;
dp[0] = 0;
for(int i = 1;i < s.size();i++){
if(s[dp[i-1]] == s[i]){
dp[i] = dp[i-1] + 1;
}else{
int q = dp[i-1];
while(q != 0 && s[q] != s[i]){
q = dp[q - 1];
}
if(s[q] == s[i]){
q++;
}
dp[i] = q;
}
if(dp[i] >= ssol){
ans++;
if(ans <= 1000){
sol.push_back(i - 2 * ssol);
}
}
//cout << dp[i] << " ";
}
out << ans << '\n';
for(int i = 0;i < sol.size();i++){
out << sol[i] << ' ';
}
}
int main() {
string a, b;
in >> a >> b;
a.push_back('#');
s = a + b;
solve(a.size() - 1);
return 0;
}