poj1056（字符串判断是否存在一个字符串是另一个字符串的前缀）

题目链接：https://vjudge.net/problem/POJ-1056

题意：给定一个字符串集，判断是否存在一个字符串是另一个字符串的前缀。

思路：和hdoj1671一样，有两种情况：

　　当前长度处已经存在字符串。比如先插入10，再插入101。

　　最后一个字符后面还有子结点。比如先插入101，再插入10。

AC code：

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=1e6+;

int cas,trie[maxn][],key[maxn],cnt,flag;

char str[];

void insert(char *s){

    int len=strlen(s),u=;

    for(int i=;i<len;++i){

        int t=s[i]-'';

        if(!trie[u][t]){

            ++cnt;

            memset(trie[cnt],,sizeof(trie[cnt]));

            key[cnt]=;

            trie[u][t]=cnt;

        }

        u=trie[u][t];

        if(key[u]){

            flag=;

            return;

        }

        if(i==len-) key[u]=;

    }

    if(trie[u][]||trie[u][]) flag=;

}

int main(){

    while(~scanf("%s",str)){

        flag=,cnt=;

        memset(trie[],,sizeof(trie[]));

        insert(str);

        while(scanf("%s",str),str[]!='')

            if(flag) insert(str);

        if(flag) printf("Set %d is immediately decodable\n",++cas);

        else printf("Set %d is not immediately decodable\n",++cas);

    }

    return ;

}

poj1056（字符串判断是否存在一个字符串是另一个字符串的前缀）的相关教程结束。