Submission #683056

#TimeUsernameProblemLanguageResultExecution timeMemory
683056Ahmed57Savez (COCI15_savez)C++14
0 / 120
67 ms64008 KiB
#include <bits/stdc++.h> using namespace std; #define int long long //Hashing long long a1 = 911382323 , mod1 = 972663749; long long a2 = 37 , mod2 = 1000000007; vector<long long> h1(1000001),h2(1000001),p1(1000001),p2(1000001); long long has(string s){ h1[0] = 0 , h2[0] = 0; for(int i = 0;i<s.size();i++){ h1[i+1] = (h1[i]*a1+((s[i]-'a')+1))%mod1; h2[i+1] = (h2[i]*a2+((s[i]-'a')+1))%mod2; } } long long q1(int l,int r){return(((h1[r]-h1[l-1]*p1[r-l+1])%mod1)+mod1)%mod1;} long long q2(int l,int r){return(((h2[r]-h2[l-1]*p2[r-l+1])%mod2)+mod2)%mod2;} signed main(){ int n; cin>>n; p1[0] = 1 , p2[0] = 1; for(int i = 1;i<=1e6;i++){ p1[i] = (p1[i-1]*a1)%mod1; p2[i] = (p2[i-1]*a2)%mod2; } map<string,int> dp; long long ma = 0; for(int i = 0;i<n;i++){ string s;cin>>s; has(s); string v; long long mi = 0; for(int i = 1;i<=s.size();i++){ v+=s[i-1]; if(q1(1,i)==q1((s.size()-i)+1,s.size())&&q2(1,i)==q2((s.size()-i)+1,s.size())){ mi = max(mi,dp[v]); } } dp[s] = mi+1; ma = max(ma,dp[s]); } cout<<ma; }

Compilation message (stderr)

savez.cpp: In function 'long long int has(std::string)':
savez.cpp:13:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
savez.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | }
      | ^
savez.cpp: In function 'int main()':
savez.cpp:35:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i = 1;i<=s.size();i++){
      |                       ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...