intshortPalindrome(string s){ int dp[26][26] = {}; // how many possible matches a after b int dpp[26] = {}; // how many matched b c in dpp[index] int freq[26] = {}; int res = 0, mod = 1e9 + 7;
for(auto& ch : s) { int index = ch - 'a';
//add a b c [ch] previous matched result // use char as d res = (res + dpp[index]) % mod;
// update matched count // use char as c for(int i = 0; i < 26; i++) dpp[i] = (dpp[i] + dp[i][index]) % mod;
// update how many machted next time // use char as b for(int i = 0; i < 26; i++) dp[i][index] = (dp[i][index] + freq[i]) % mod;