B-Trieツリー（文字列問題）
4994 ワード
/*http://acmore.net:8080/contest/view.action?cid=11#problem/B B-TrieツリーTime Limit：2000 MS メモリLimit：65536 KB 64 bit IO Format:%I 64 d&%I 64 u Submit Status Description You、as a member of a development team for a new spell check program、ar to write a module that will check the corectnes of given words using a known dictionary of all corectwords.ins. If the word is absent in the dictionation ary the n it can be replace d by corectwords(from the dict ary)that can be obatained by one of the following operation:？deleting of one letter from the word； ?replecng of one letter in the word with an arbitrary letter； ?inserting of one arbitrary letter into the word. Your task is to write the program that will find all possible replaccements from the dictionary for evergiven word. Input The first part of the input file contains all words from the dictionary.Each word occupies its own line.This parts finished by the single character's's.All world arets.The mofferenter。 The next part of the file contains all words that are to be checked.Each word occupies its own line.This parts also finished by the single character's.The will be most 50 worketed.The will atbe。 All words in the input file（wods from the dictionary and words to be checed）consist only of small alphabeetic characters and each one contains 15 characters most. Output Write to the output file exactly one line forevevrychcheced wod in the order of theirapearance in the second partof the inputfile.If the wod iscorect（i.e.it existsin the dictorororary）wthetherite thethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethetherererererereststststststininininininininininininininininininininininininininininininininininininininininininininininininininlon）and after a single space write all its possible replaccements、separated by spaces.The replaccements shorororordes of their aaapearance in the dictary(Inthe first part of the input file).If there are e e e e e e e e replacmentsforthiswod the the inininininininininininininininininininininininininininininininininininininininininininininininininininininststststststststststststststststststststststststststststststststststststststststststststststststststststststthethecontest hav oo or i fi mre〓Sample Output me is corect aware:award m:i my me contest is corect hav:has have oo:too or:i is corect fi:i mre:more me題意：一連の辞書単語を提供します。 また、一連の検索単語を提供して、辞書語からこの単語を探します。この単語が辞書に出たら、その単語は「is corect」です。 そうでないと、辞書の単語に出てくる順番によって、出力と単語の違いはアルファベットの辞書語だけです。（ここの違いはアルファベットを挿入または削除または置換することです。）考え方：最初は辞書の木を使いたいですが、この違いを見つけるためのアルゴリズムはまだ考えられません。その後、テーマのデータが小さいので、暴力法で分類し、以下のコードを比較します。364 KB 188 ms C++2037 B 2013-04-25 */
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
const int maxn=50000+10;
char dic[maxn][20],word[55][20];
int n,m;
char temp[maxn][20];
int len;
int cmp(char s1[],char s2[])
{
int cnt=0;
int i,j,k;
int len1=strlen(s1);
if(len1-len==1)//
{
for(j=0,i=0;j<len1,i<len;j++,i++)
{
while(s2[i]!=s1[j]&&j<len1)
{
cnt++;
j++;
}
if(cnt>1)
return cnt;
}
if(cnt==0)
cnt=1;
}
else if(len-len1==1)//
{ for(i=0,j=0;j<len1,i<len;i++,j++)
{
while(s2[i]!=s1[j]&&i<len)
{cnt++;
i++;
}
if(cnt>1)
return cnt;
}
if(cnt==0)
cnt=1;
}
else if(len1==len)//
{
for(i=0;i<len;i++)
{
if(s2[i]!=s1[i])
{cnt++;
}
if(cnt>1)
return cnt;
}
}
else cnt=-1;
return cnt;
}
void work()
{ int ok,k,t,p;
for(int i=0;i<m;i++)
{ k=0;
ok=0;
len=strlen(word[i]);
for(int j=0;j<n;j++)
{p=cmp(dic[j],word[i]);
//printf("%d ",p);
if(p==1)
strcpy(temp[k++],dic[j]);
if(p==0)
{
ok=1;
break;
}
}
if(ok)
printf("%s is correct
",word[i]);
else
{printf("%s:",word[i]);
for(t=0;t<k;t++)
{ if(t<k)
printf(" ");
printf("%s",temp[t]);
}
printf("
");
}
}
}
int main()
{
n=0;
m=0;
int i,j;
j=i=0;
for(;;)
{scanf("%s",dic[i++]);
if(dic[i-1][0]=='#')
{n=i-1;
break;
}
}
for(;;)
{scanf("%s",word[j++]);
if(word[j-1][0]=='#')
{m=j-1;
break;
}
}
work();
return 0;
}