Pagini recente » Cod sursa (job #684113) | Cod sursa (job #1096859) | Cod sursa (job #381177) | Cod sursa (job #1245877) | Cod sursa (job #2838507)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const NMAX = 2e6;
int dp[1 + NMAX];
string s;
vector <int> sol;
bool isEqual(int siz, int lim) {
for(int i = 0;i < siz;i++){
if(s[i] != s[lim - siz + i + 1]){
return false;
}
}
return true;
}
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{
dp[i] = dp[i-1];
while(!isEqual(dp[i], i)){
dp[i]--;
}
}
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;
}