我以為像a、aa這樣的輸入應該是沒有輸出的,結果還是要輸出aa。
建樹的時候就是常規建樹,不過查找的時候要做一些變形:對于一個單詞,從第一位檢查有沒有單詞是它的前綴,如果有的話,再去檢查它的后半部分是不是一個獨立的單詞,要滿足這兩次查找才能輸出。
題意:給一些單詞(以字典序輸入),找出那些可以分成另外的兩個單詞的單詞,以字典序輸出;
?
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef struct Node
{
??? int flag;
??? struct Node *next[26];
}Node,*Tree;
char a[50001][30];
void Creat(Tree &T)
{
??? T=(Node *)malloc(sizeof(Node));
??? T->flag=0;
??? for(int i=0;i<26;i++)
??? {
??????? T->next[i]=NULL;
??? }
}
void insert(Tree &T,char *s)
{
??? Tree p=T;
??? int t;
??? int l=strlen(s);
??? for(int i=0;i<l;i++)
??? {
??????? t=s[i]-'a';
??????? if(p->next[t]==NULL)
??????? {
??????????? Creat(p->next[t]);
??????? }
??????? p=p->next[t];
??? }
??? p->flag=1;
}
int search(Tree T,char *s)
{
??? int t;
??? Tree p=T;
??? int l=strlen(s);
??? for(int i=0;i<l;i++)
??? {
??????? t=s[i]-'a';
??????? if(p->next[t]==NULL)
??????????? return 0;
??????? p=p->next[t];
??? }
??? if(p->flag) return 1;
??? else return 0;
}
void D(Tree p)
{
??? for(int i=0;i<26;i++)
??? {
??????? if(p->next[i]!=NULL)
??????????? D(p->next[i]);
??? }
??? free(p);
}
int main()
{
???? char s1[30];
???? char s2[30];
???? Tree T;
???? int kk=0;
???? Creat(T);
???? while(gets(a[kk])&&strlen(a[kk]))
???? {
???????? insert(T,a[kk]);
??????? kk++;
???? }
???? int i,j;
???? for(i=0;i<kk;i++)
???? {
???????? int l=strlen(a[i]);
???????? for(j=0;j<l;j++)
???????? {
???????????? memset(s1,'\0',sizeof(s1));
???????????? memset(s2,'\0',sizeof(s2));
???????????? int kkk=0;
???????????? int jjj=0;
???????????? for(int kk=0;kk<=j;kk++)
??????????????? s1[kkk++]=a[i][kk];
????????????? for(int jj=j+1;jj<l;jj++)
????????????? {
????????????????? s2[jjj++]=a[i][jj];
????????????? }
????????????? int qq=search(T,s1);
????????????? int ww=search(T,s2);
????????????? if(qq&&ww)
????????????? {
????????????????? printf("%s\n",a[i]);
????????????????? break;
????????????? }
?????????????
???????? }
???? }
???? D(T);
??? return 0;
}