Articles12
Tags2
Categories0

LuoGuP1470【最长前缀LongestPrefix】

反正题解没人看 就提供个思路吧

Trie+DFS 每搜到一个节点看它是不是一个单词的终点,是就加一个搜索路径,不是就按照Trie的Find()模板进行DFS. 优化:记得加vis数组进行记忆化搜索,不然会有重复情况会TLE。

上代码

#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);
}
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2019/11/04/LuoGuP1470%E3%80%90%E6%9C%80%E9%95%BF%E5%89%8D%E7%BC%80LongestPrefix%E3%80%91/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可