oj.uz

Submission #67434

# Submission time Handle Problem Language Result Execution time Memory
67434 2018-08-14T09:24:04 Z KLPP Palindromes (APIO14_palindrome) C++14
Compilation error
 0 ms 0 KB 
#include<iostream>
#include<map>
using namespace std;
typedef long long int lld;
#define MOD 1000000007
#define BASE 257
lld hash2[1000000];
lld hash[1000000];
lld pow[1000000];
int n;
bool palindrome(int a, int b){
	lld A=hash[b+1]-hash[a];
	A*=pow[n-1-a];
	lld B=hash2[a]-hash2[b+1];
	B*=pow[b];
	A%=MOD;
	B%=MOD;
	if(B<0)B+=MOD;
	if(A<0)A+=MOD;
	//cout<<a<<" "<<b<<" "<<A<<" "<<B<<endl;
	if(A%MOD==B%MOD)return true;
	return false; 
}
lld val(int a, int b){
	lld A=hash[b+1]-hash[a];
	A*=pow[n-1-a];
	A%=MOD;
	if(A<0)A+=MOD;
	return A; 
}
int main(){
	string s;
	cin>>s;
	n=s.size();
	hash[0]=0;
	lld v=1;
	for(int i=1;i<=n;i++){
		hash[i]=(s.at(i-1))*v+hash[i-1];
		hash[i]%=MOD;
		pow[i-1]=v;
		v*=BASE;
		v%=MOD;
	}
	hash2[n]=0;
	v=1;
	for(int i=n-1;i>-1;i--){
		hash2[i]=(s.at(i))*v+hash2[i+1];
		hash2[i]%=MOD;
		v*=BASE;
		v%=MOD;
	}
	//cout<<hash2[0]<<" "<<hash[n]<<endl;
	lld ans=0;
	for(lld len=1;len<=n;len++){
		map<lld,int> m;
		//cout<<hash[i]<<" "<<hash2[i]<<endl;
		for(int i=0;i+len-1<n;i++){
			if(palindrome(i,i+len-1)){
				lld H=val(i,i+len-1);
				map<lld,int>::iterator it=m.find(H);
				if(it==m.end()){
					m[H]=1;
					ans=max(ans,len);
					//cout<<len<<endl;
				}else{
					it->second++;
					ans=max(ans,it->second*len);
					//cout<<it->second*len<<endl;
				}
			}
		}
		//cout<<(hash[i]+hash2[i])%MOD<<endl;
	}cout<<ans<<endl;
	//cout<<palindrome(0,2)<<endl;
	
}

Compilation message

palindrome.cpp: In function 'bool palindrome(int, int)':
palindrome.cpp:12:8: error: reference to 'hash' is ambiguous
  lld A=hash[b+1]-hash[a];
        ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:12:18: error: reference to 'hash' is ambiguous
  lld A=hash[b+1]-hash[a];
                  ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp: In function 'lld val(int, int)':
palindrome.cpp:25:8: error: reference to 'hash' is ambiguous
  lld A=hash[b+1]-hash[a];
        ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:25:18: error: reference to 'hash' is ambiguous
  lld A=hash[b+1]-hash[a];
                  ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:35:2: error: reference to 'hash' is ambiguous
  hash[0]=0;
  ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:38:3: error: reference to 'hash' is ambiguous
   hash[i]=(s.at(i-1))*v+hash[i-1];
   ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:38:25: error: reference to 'hash' is ambiguous
   hash[i]=(s.at(i-1))*v+hash[i-1];
                         ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~
palindrome.cpp:39:3: error: reference to 'hash' is ambiguous
   hash[i]%=MOD;
   ^~~~
palindrome.cpp:8:5: note: candidates are: lld hash [1000000]
 lld hash[1000000];
     ^~~~
In file included from /usr/include/c++/7/bits/basic_string.h:6575:0,
                 from /usr/include/c++/7/string:52,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^~~~