codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
class Solution { public: string s; long long mul = 37; long long mod = 1000000007; long long h[2005]; long long p[2005]; void build(string s){ long long cur = 0; long long now = mul; p[0] = 1; for(int i = 1 ; i <= (int)s.size();i++){ p[i] = now; now *= mul; now %= mod; } for(int i = 1 ; i <= (int)s.size() ; i ++){ cur *= mul; cur += (int)s[i-1]; cur %= mod; h[i] = cur; } } long long get(int l,int r){ long long ret = (h[r] - (h[l-1] * p[r - l + 1] % mod) + mod) % mod; return ret; } int distinctEchoSubstrings(string text) { int ret = 0; s = text; build(s); set<long long>st; for(int i = 1 ; i <= text.size()/2 ; i++){ int cur = 0; for(int j = i ; j < text.size() ; j++){ if(text[j] == text[j-i]){ cur++; } else{ cur = 0; } if(cur >= i){ st.insert(get(j-i*2+2,j+1)); } } } return st.size(); } };
Private
[
?
]
Run code
Submit