题解 P1470 【最长前缀 Longest Prefix】
NoobYlh
2019-09-23 12:30:19
（~~反正题解没人看 就提供个思路吧~~）
Trie+DFS 每搜到一个节点看它是不是一个单词的终点，是就加一个搜索路径，不是就按照Trie的Find()模板进行DFS.
优化：记得加vis数组进行记忆化搜索，不然会有重复情况会TLE。
上代码
------------
```cpp
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=5050;
const int INF = 0x3f3f3f3f;
int tree[maxn][30];
bool vis[2020][200020];
int ed[maxn];
char que[200020];
char ch[20];
int n,cnt,Len;
int ans=0;
int newnode(){
for(int i=0;i<=26;i++){
tree[cnt][i]=-1;
}
ed[cnt]=0;
return cnt++;
}
void init(){
cnt=0;
newnode();
}
void insert(){
int len=strlen(ch);
int root=0;
for(int i=0;i<len;i++){
int x=ch[i]-'A';
if(tree[root][x]<=0){
tree[root][x]=newnode();
}
root=tree[root][x];
}
ed[root]=1;
}
void dfs(int pos,int len){
if(vis[pos][len]) return;
vis[pos][len]=1;
int x=que[len]-'A';
if(ed[pos]){
ans=max(ans,len);
}
if(len==Len){
return;
}
if(tree[pos][x]!=-1){
dfs(tree[pos][x],len+1);
}if(ed[pos]){
dfs(0,len);
}
}
int main(){
init();
while(scanf("%s",ch)&&strcmp(ch,".")){
insert();
}
Len=0;
while(scanf("%s",que+Len)!=EOF){
Len=strlen(que);
}
dfs(0,0);
printf("%d\n",ans);
}
```