#include <bits/stdc++.h>
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int inf = 0x3f3f3f3f ;
const int MAXN = 1010 ;
const int ALF = 30 ;
const int SZTRIE = MAXN*MAXN ;
using namespace std ;
//Se der errado, checar o limite da trie
struct Trie
{
int trie[SZTRIE][ALF] , nodes ;
ll qtd[SZTRIE] ;
Trie()
{
memset(trie,0,sizeof trie ) ;
memset(qtd,0,sizeof qtd) ;
nodes = 0 ;
}
void add(char str[] , int l , int r)
{
int cur = 0 ;
for(int i = l ; i < r ; i++ )
{
int c = str[i] - 'a' ;
if( trie[cur][c] == 0 ) trie[cur][c] = ++nodes ;
cur = trie[cur][c] ;
}
qtd[cur] ++ ;
}
ll findQtd(char str[] , int l , int r)
{
int cur = 0 ;
for(int i = l ; i < r ; i++ )
{
int c = str[i]-'a' ;
if(trie[cur][c] == 0) return 0 ;
cur = trie[cur][c] ;
}
return qtd[cur] ;
}
} ;
int n ;
char str[MAXN] ;
bool s[MAXN][MAXN] ;
Trie myTrie ;
void findPalindrome()
{
lp(i,0,n) s[i][i] = true ;
lp(i,0,n-1)
if( str[i] == str[i+1] ) s[i][i+1] = true ;
lp(i,2,n)
for(int j = 0 ; j + i < n ; j++ )
s[j][j+i] = ( s[j+1][j+i-1] && (str[j]==str[j+i]) ) ;
}
int main()
{
scanf(" %s", str ) ;
n = strlen(str) ;
findPalindrome() ;
lp(i,0,n)
lp(j,i, n) myTrie.add(str,i,j+1) ;
ll ans = 0 ;
lp(i,0,n)
lp(j,i,n)
if(s[i][j])
ans = max(ans, myTrie.findQtd(str, i , j+1)*(j-i+1) ) ;
printf("%lld\n" , ans );
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", str ) ;
~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
128120 KB |
Output is correct |
2 |
Correct |
108 ms |
128120 KB |
Output is correct |
3 |
Correct |
108 ms |
128120 KB |
Output is correct |
4 |
Correct |
108 ms |
128092 KB |
Output is correct |
5 |
Correct |
107 ms |
128120 KB |
Output is correct |
6 |
Correct |
107 ms |
128124 KB |
Output is correct |
7 |
Correct |
108 ms |
128028 KB |
Output is correct |
8 |
Correct |
124 ms |
128164 KB |
Output is correct |
9 |
Correct |
109 ms |
128120 KB |
Output is correct |
10 |
Correct |
109 ms |
128092 KB |
Output is correct |
11 |
Correct |
108 ms |
128120 KB |
Output is correct |
12 |
Correct |
109 ms |
128120 KB |
Output is correct |
13 |
Correct |
109 ms |
128132 KB |
Output is correct |
14 |
Correct |
109 ms |
128120 KB |
Output is correct |
15 |
Correct |
108 ms |
128120 KB |
Output is correct |
16 |
Correct |
108 ms |
128120 KB |
Output is correct |
17 |
Correct |
109 ms |
128076 KB |
Output is correct |
18 |
Correct |
109 ms |
128184 KB |
Output is correct |
19 |
Correct |
124 ms |
128196 KB |
Output is correct |
20 |
Correct |
109 ms |
128120 KB |
Output is correct |
21 |
Correct |
109 ms |
128248 KB |
Output is correct |
22 |
Correct |
109 ms |
128248 KB |
Output is correct |
23 |
Correct |
109 ms |
128248 KB |
Output is correct |
24 |
Correct |
126 ms |
128248 KB |
Output is correct |
25 |
Correct |
113 ms |
128248 KB |
Output is correct |
26 |
Correct |
113 ms |
128188 KB |
Output is correct |
27 |
Correct |
109 ms |
128120 KB |
Output is correct |
28 |
Correct |
130 ms |
128248 KB |
Output is correct |
29 |
Correct |
131 ms |
128248 KB |
Output is correct |
30 |
Correct |
109 ms |
128232 KB |
Output is correct |
31 |
Correct |
109 ms |
128260 KB |
Output is correct |
32 |
Correct |
110 ms |
128276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1060 ms |
129044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
312 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
308 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
343 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |