当前位置：首页 > news >正文

Broken Space Bar（Trie）[待补]

news 来源：原创 2024/5/10 9:08:19

题目链接

在这里插入图片描述
1.给出一个字典，现在还有一串无空格的数，判断该串是否能由字典中若干单词串联形成

2.标答是构建字典树贪心选择长度最长的，即如果字典有orz，orzdd，序列有orzdd，那么会优先选orzdd

3.这题标答是错的，尽管能过题，只能说明题目数据太水，并不能说明代码正确。设想如果有的单词有公共前后缀，除了公共部分剩余的后缀前缀均在序列，例如：
1
orz
orzdd
ddab
1
orzddab
按标答来说是找不到的，但是事实上是可以由"orz"和"ddab"组成，因此这里感觉是要用递归判断，而如何递归也很麻烦，暂时没写出来，放着以后研究

待改进代码：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
int a[105];

struct Trie{
    int Next[maxn][26],tot;
    int num[maxn];           //该结点结尾的字符串是否存在

    void init(){
        tot=0;
        memset(num,0,sizeof num);
        memset(Next,0,sizeof Next);
    }

    void insert(char *s,int k){    //插入字符串
        int p=0,len=strlen(s);
        for(int i=0;i<len;i++){
            int c=s[i]-'a';
            if(!Next[p][c]) Next[p][c]=++tot;  //没有就添加结点
            p=Next[p][c];
        }
        num[p]=k;
    }

    int find(char *s){    // 查找字符串
        int p=0,cnt=0,len=strlen(s);
        for(int i=0;i<len;i++){
            p=Next[p][s[i]-'a'];
            if(num[p] && (!Next[p][s[i+1]-'a'] || i==len-1)){
                a[cnt++]=num[p];
                p=0;
            }else if(!num[p] && !Next[p][s[i+1]-'a']){
                return 0;
            }
        }
        return cnt;
    }
}trie;

char s[105][105],str[55];;


int main(){
	int n,t,kase=0;
	while(~scanf("%d",&n) && n){
		trie.init();
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]);
			trie.insert(s[i],i);
		}
		scanf("%d",&t);
		printf("Data set #%d:\n",++kase);
		for(int i=0;i<t;i++){
			scanf("%s",str);
			memset(a,0,sizeof(a));
			int ans=trie.find(str);
			if(!ans){
				printf("     %s --- misspelled word\n",str);
			}else if(ans==1){
				printf("     %s --- the word is in dictionary\n",str);
			}else{
				printf("     %s --- the word is concatenation of\n",str);
				for(int j=0;j<ans;j++){
					printf("          %s\n",s[a[j]]);
				}
			}
		}
		printf("\n");
	}
	return 0;
}