# BZOJ 1174: [Balkan2007]Toponyms

## Output

a single line with an integer representing the maximal level of complexity Lc(T).

## Sample Input

7 Jora de Sus Orhei Jora de Mijloc Joreni Jora de Jos Japca Orheiul Vechi

24

## HINT

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int n,sz=1,ans;
6 string ch;
7 int a[500001][53],f[500001];
8 void insert()
9 {
10     int l=ch.length(),now=0;
11     for(int i=0;i<l;i++)
12     {
13         int t;
14         if(ch[i]==' ')t=52;
15         else if(ch[i]<='Z')t=ch[i]-'A';
16         else t=ch[i]-'a'+26;
17         if(a[now][t])now=a[now][t];
18         else now=a[now][t]=++sz;
19         f[now]++;
20         ans=max(ans,f[now]*(i+1));
21     }
22 }
23 int main()
24 {
25     scanf("%d",&n);
26     for(int i=1;i<=n;i++)
27     {
28        getline(cin,ch);
29        insert();
30     }
31     printf("%d",ans);
32     return 0;
33 }```

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstring>
6 #include<algorithm>
7 #include<queue>
8 using namespace std;
9 const int MAXN=1001;
11 {
12     char c='+';bool flag=0;n=0;
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')n=n*10+c-48,c=getchar();
15 }
16 struct E
17 {
18     int u,v,nxt;
19 }edge[MAXN];
21 int num=1;
22 struct node
23 {
24     int bh;
25     int num;
26     int val;
27     node(){num=0;val=0;}
28 }trie[MAXN];
29 int tot=0;
30 char a[MAXN];
31 bool vis[MAXN];
32 inline void add_edge(int x,int y)
33 {
34     edge[num].u=x;
35     edge[num].v=y;
38 }
39 long long int ans=0;
40 inline void insert(char *a)
41 {
42     int l=strlen(a);int now=0;
43     for(register int i=0;i<l;i++)
44     {
45         bool flag=0;
46         int debug=a[i];
48         {
49             if(trie[edge[j].v].val==a[i])
50                 trie[edge[j].v].num++,
51                 flag=1,
52                 now=edge[j].v;
53         }
54         if(flag==0)
55             {
56                 trie[++tot].bh=tot;
57                 trie[tot].num=1;
58                 trie[tot].val=a[i];
60                 now=tot;
61             }
62         ans=max(ans,(long long )(i+1)*trie[now].num);
63     }
64 }
65 int main()
66 {
68     int n;
70     for(int i=1;i<=n;i++)
71     {
72         memset(a,0,sizeof(a));int hh=0;
73         char ch=getchar();bool flag2=0;
74         while(ch=='\n')    ch=getchar();
75         while(ch!='\n')
76             a[hh++]=ch,ch=getchar();
77         insert(a);
78     }
79     printf("%lld",ans);
80     return 0;
81 }```

``` 1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #define N 5000010
5 using namespace std;
6 int tot = 1 , head[N] , to[N] , next[N] , cnt , si[N];
7 char val[N];
8 void add(int x , int y , char c)
9 {
10     to[++cnt] = y , val[cnt] = c , next[cnt] = head[x] , head[x] = cnt;
11 }
12 int main()
13 {
14     int n , i , j , k , t , p;
15     char ch;
16     long long ans = 0;
17     scanf("%d" , &n);
18     for(i = 1 ; i <= n ; i ++ )
19     {
20         ch = getchar();
21         while(ch == '\n') ch = getchar();
22         for(j = t = 1 ; ch != '\n' ; j ++ , ch = getchar())
23         {
24             for(p = 0 , k = head[t] ; k ; k = next[k])
25             {
26                 if(val[k] == ch)
27                 {
28                     p = to[k];
29                     break;
30                 }
31             }
32             if(!p) add(t , p = ++tot , ch);
33             t = p , si[t] ++ , ans = max(ans , (long long)j * si[t]);
34         }
35     }
36     printf("%lld\n" , ans);
37     return 0;
38 }```

1811 篇文章115 人订阅

0 条评论

## 相关文章

### 基础野：细说无符号整数

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

2046

2549

36613

3175

6105

1063

### 对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会...

2262

3465

1473

### Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element ...

2776