C++ Rabin Karp Algorithm || Easy Implementation
\ntypedef long long  ll;\nclass Solution {\npublic:\n    ll mod = 100000000007;\n    ll dp[1005],pa[1005];\n    void preProcess(string s){\n        ll p = 29; /
```\ntypedef long long  ll;\nclass Solution {\npublic:\n    ll mod = 100000000007;\n    ll dp[1005],pa[1005];\n    void preProcess(string s){\n        ll p = 29; // any prime no.\n        ll pow = p;\n\n        dp[0] = s[0] - \'a\' + 1;\n        pa[0] = 1;\n        for(ll i = 1;i < s.length();i++){\n            dp[i] = (dp[i-1] + (s[i] - \'a\' + 1) * pow) % mod;\n            pa[i] = pow;\n            pow *= p;\n            pow %= mod;\n        }\n    }\n \n    ll hashQuery(ll l, ll r){\n        ll ans = dp[r];\n        if(l > 0)\n            ans = (ans - dp[l - 1] + mod) % mod;\n        return ans;\n    }\n    vector<int> sumPrefixScores(vector<string>& words) {\n        map<ll, int> m;\n        int n = words.size();\n        for(int i = 0;i < n;i++){\n            string s = words[i];\n            memset(dp, 0, sizeof(dp));\n            memset(pa, 0, sizeof(pa));\n            preProcess(s);\n            ll sum1 = 0;\n            \n            for(int j = 0;j < s.length();j++){\n                ll pref = hashQuery(0, j);\n                m[pref]++;\n            }\n        }\n        vector<int> ans(n);\n        for(int i = 0;i < n;i++){\n            string s = words[i];\n            ll sum1 = 0,sum2 = 0;\n            memset(dp, 0, sizeof(dp));\n            memset(pa, 0, sizeof(pa));\n            preProcess(s);\n            for(int j = 0;j < s.length();j++){\n                ll pref = hashQuery(0, j);\n                sum2 += m[pref];\n            }\n            ans[i] = sum2;\n        }\n        \n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C']