poj 1035

关于图论的一些问题暂时到此结束，下面进入数据结构专题，首先讨论串的问题：

题意：

先输入一个字典，再输入一些字符串，在字典里找到与该字符串相同的单词，若没有，找到与其差一个的单词：多一个字符or少一个字符or错一个字符

输入：

一个字典，#结束

输入n个字符串，在字典中查找，一共有五种情况：

输出：

** is correct

String: string1 string 2

关于输出的操作，一共分为五种情况 a:两个单词完全一致，则输出 **is correct

如果长度相差为一或者为O（有一个单词不一样），这时有二种情况，1： 相差为一（分为两种情况1：大于一2：小于一）；2：相差为0；b:单词长度相差大于等于二，则不输出结果。

针对这五种情况讨论即可：

思路：

输入的字符串一共有5中情况：

1、和字典里匹配成功，输出“正确”

2、删除一个可以匹配

3、插入一个可以匹配

4、更改一个可以匹配

5、其他情况

代码如下：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

char s[20];  
int n,size=0;        
string v,a[10010],b[10010]; 

bool cmp(string s1,string s2)

{//如果比较的串和字典中的串长度差的为-1.0.1：

       int s=0;  
	   string t;  
	   if(s1.size()>s2.size())  //s1>s2大就交换，保证s2>=s1
	   {
		   t=s1;
		   s1=s2;
		   s2=t;
	   } 

       if(s1.size()<s2.size()) //就是a!=b，大于的话已经交换了
	   {
		   s=0;     
		   for(int i=0;i<s2.size()&&s<s1.size();i++)    
			   if(s1[s]==s2[i]) 
				   s++;
			   if(s==s1.size())      
				   return true; //因为b=a+1,所以只有一个不一样的话，删除一个就是正确的
	   }//end if 完成了2、删除一个就正确 3、插入一个就正确
	   else//长度相等的话
	   {
		   s=0;       
		   for(int r=0;r<s1.size();r++)      
			   if(s1[r]==s2[r]) s++;   
			   if(s==s1.size()-1)         
				   return true;//s为匹配的个数如果有且只有一个不一样的
	   }//完成了4、更改一个正确   
	   return false;
}//end of cmp

int main()

{    
	while(scanf("%s",s)!=EOF)  
	{ //输入字典：

              if(!strcmp(s,"#")) break; 

              b[size]=s;

              a[size]=s;

              ++size;

       }   

       sort(a,a+size);  //对a排序 (默认为升序)

       //a的存在只是为了查找一样的，后面没用了。

       while(scanf("%s",s)!=EOF)  

       { //输入要查的字    

              if(!strcmp(s,"#")) break;    

              v=s;      

              n=v.size();       

              if(binary_search(a,a+size,v)) //从a开始到a+size找和v相同的,//用二分查找（折半查找和v相同的）1、若存在，则输出* is correct  
			  {
				  cout << v << " is correct\n" ;
				  continue;
			  } 

              cout << v <<": ";

       //     同printf("%s: ",v.c_str());

              int i;

              for(i=0;i<size;i++)     

              {//从头到尾搜索字典。。。。           

                     if(b[i].size()<n-1||b[i].size()>n+1)

                            continue;

//若打错的字和字典里的字相差2位或者2位以上，无匹配

                     if(cmp(b[i],v)) 

//若打错的字和字典里的字相差1位或者不差，则可能可以通过2、3、4种方法改正 

                            cout<< b[i] <<" ";

       //     同printf("%s ",b[i].c_str());   

              }      

              cout<<endl;

       } //end while  

       return 0;

}