如何实现英语单词的模糊查询？
比如说:
'?'代表一个字符，'*'代表任意字符。
输入首字符不可以是'?'或'*'。
假设有以下字符:abc,abcdefghij,abj,abcabc,abcdefghijc,bcd,abcbcd
输入:a*c
输出:abc,abcabc,abcdefghijc
输入:a????c
输出:abcabc
输入:a?c*
输出:abc,abcdefghij,abcabc,abcdefghijc,abcbcd
<功能就像文曲星里面的单词模糊查询。>
请大家给点建议,如何用Visual C++实现.
问题点数：0、回复次数：14Top
1 楼vcshcn（黑天的猩猩）回复于 2003-05-01 02:30:21 得分 0
如果我做，自己编字符串匹配Top
2 楼HeroFay（萧飞）回复于 2003-05-01 18:24:36 得分 0
认真接分是什么意思？Top
3 楼21st_centry_fox（花不归）回复于 2003-05-01 18:29:09 得分 0
哈哈
等我现在
其实这个就是字符串比较的问题，看上去没有什么难的Top
4 楼SwordMan2001（天笑2001）回复于 2003-05-02 00:37:13 得分 0
markTop
5 楼kkxxwolf（mike liu）回复于 2003-05-02 01:46:31 得分 0
你说的似乎是正则表达式。去网上搜搜，就能找出一大堆免费代码。Top
6 楼aiyinsitan（OhShit!) (Marlboro）回复于 2003-05-02 02:16:07 得分 0
可以参考C++ Primer中的文本查询系统, 第十七章Top
7 楼ghtsao（月之暗面）回复于 2003-05-02 03:49:29 得分 0
很多语言里都支持正则表达式，直接就可以用。Top
8 楼21st_centry_fox（花不归）回复于 2003-05-02 21:33:08 得分 0
呵呵，我把这个程序的核心（比较目标词汇和库词汇）写出来了，只要你再绐我一个词库，我就可以很快的绐你产品了：）
在DEV Ｃ＋＋和 ｖｃ６下都试过
在主程序里我简单的试了一下，可以的，
你再顺便帮我测试一下吧：
#include <iostream>
#include <cstdlib>
using namespace std;
bool compare(char * module, char * source, int mlen, int slen)
{
if (mlen > slen) return false;
else if (mlen == 1 || slen == 1) return true;
// Notice here should be mlen - 1 not just mlen for there is an '\0' in the array
else for (int i = 0; i < mlen - 1; i++)
{
if (module[i] == '?');
else if (module[i] == '*')
{
for (int j = 0; j <= slen - mlen; j++)
{
if(compare(module + i + 1, source + i + 1 + j, mlen - i - 1, slen - i - 1 - j)) return true;
}
}
else if (module[i] != source[i]) return false;
}
return true;
}
int main()
{
char module[] = "ia??o*e";
char source[] = "iamfoxhuylex";
cout << "The result of the comparising of the two strings :";
if ( compare(module, source, sizeof(module), sizeof(source)) )
cout << " okay they match each other\n";
else
cout << " they do not pair\n";
system("pause");
}Top
9 楼SwordMan2001（天笑2001）回复于 2003-05-03 10:36:58 得分 0
下面的程序对于大多数情况都是可以的,包括输入首字符就是'?'或'*'的情况,
但对于模式中有多个*的情况, 不能保证完全正确(但绝大多数是正确的)
楼主可以自己调试着看一看, 程序中输入Ctrl-Z结束, 输入m修改模式.
#include <iostream>
using namespace std;
void SetFailLink(char *module, int failLink[], int len)
{
int i;
for (i=0; i<len && module[i]!='*'; i++)
failLink[i]=-1;
if(i<len){
int j;
// failLink[j]=-2;
for(j=i; j<len; j++)
failLink[j]=i;
}
}
bool match(char * module, char * source)
{
int mlen=strlen(module), slen=strlen(source);
int *failLink=new int[mlen];
SetFailLink(module, failLink, mlen);
int i=0, state=0;
bool bMatch;
while (true){
if (module[state]=='*'){
if (++state == mlen)
{bMatch=true; break;}//match?????
for (; i!=slen && source[i] != module[state]; i++);
if (i==slen)
{bMatch=false;break;}
}
if (source[i] == module[state] || module[state]=='?'){
++i;
if (i>=slen){
bMatch = (state==mlen-1 || (state==mlen-2 && module[state+1]=='*'));
break;
}
if(++state == mlen)
state=failLink[state-1];
}
else if((state = failLink[state]) == -1)
{bMatch=false; break;}
}
delete[] failLink;
return bMatch;
}
int main()
{
char module[20] = "a*bc";
char source[30];
cout << "To match module: "<<module<<" (Enter \"m\" to modify module)\n";
while (cin >> source){
if (strcmp(source, "m")==0){
cout<<"Input new module: ";
cin>>module;
cout << "To match module: "<<module<<"(\"m\" to modify module)\n";
continue;
}
if ( match(module, source) )
cout << " okay they match each other\n";
else
cout << " they do not pair\n";
}
system("pause");
}
Top
10 楼SwordMan2001（天笑2001）回复于 2003-05-03 10:39:04 得分 0
程序中使用了状态转换和模式匹配的有关思想, 如使用了有限状态自动机, 失败链接值等.Top
11 楼SwordMan2001（天笑2001）回复于 2003-05-03 10:51:28 得分 0
关键在于对"*"的处理,主要思想是如果p[i]=="*', 则它可以匹配任何值(包括空值),
为使情况确定化, 令它匹配除p[i+1]外的所有值,
但如果在p[i+1]后出现不匹配的情况,则可能是因为前面的"*"也应该匹配p[i+1],所以状态转到"*"处重新判断.
由上分析可知,当出现多个"*"时,由于一旦出现"*"后的不匹配,则转向第一个"*"的位置,因此可能会错过正确匹配的机会.
当然,这种情况出现的概率还是相当小的.
另外,21st_centry_fox(花不归) 的程序还有很多情况没有考虑到,可以用我的测试程序一试便知; 同时,我的程序中借用了21st_centry_fox(花不归)的一些内容, 特此声明.Top
12 楼mjohhh（s）回复于 2003-05-05 17:06:45 得分 0
下面的程序用了递归，我的测试是对如
s1=sa?*s
s2=s??k*s
的混合串 mach(s1,s2)==1,即s1==s2
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
using namespace std;
int mach(string s1,string s2);
int mach(string s1,string s2){
int ismach = 1;
int i = 0;
int j = 0;
const int len1 = s1.length();
const int len2 = s2.length();
while (i<len1 && j<len2 && ismach){
while( i<len1 && j<len2 && (s1[i]==s2[j] ||s1[i]=='?'||s2[j]=='?') ){
i++;
j++; //if 'c'='c' or 'c'='?' or '?'='c'
}
if(i<len1 &&j<len2) {
if (s1[i]=='*' ){
if (s1[len1-1]='*')return 1;
int p = s2.find_last_of(s1[++i]) ;
if (p<len2){
// if find char after '*' is also in s2
if ( mach(s1.substr(i,len1-i) ,s2.substr(p,len2-p)))
return 1;
else
ismach =0; // substr star with * is not mached
}
else ismach = 0;// not find 'x'(s1='...*x...')in s2
}
// similar operator
if(s2[j]=='*'){ if(s2[len2-1]=='*')
return 1;
int p = s1.find_last_of(s2[++j]) ;
if (len1>p && p>=0){
if(mach(s2.substr(j,len2-j) ,s1.substr(p,len1-p)))
return 1;
else ismach=0;
}
else ismach = 0;
}
else ismach = 0; // s1[i]!=s2[j]
}
else if ((i<len1 || j<len2)) //simple match falied
ismach = 0;
}
if (i>=len1 && j>=len2 && ismach)
return 1;
else
return 0;
}
void main(){
string s1;
string s2;
char c;
cin >> c;
while(c!='`'){
cout <<"input two strings:"<<endl;
cin >> s1;
cin >> s2;
if (mach(s1,s2))
cout <<"s1 == s2"<<endl;
else
cout <<"s1 != s2 "<<endl;
cin >> c;
}
}Top
13 楼mjohhh（s）回复于 2003-05-05 17:15:06 得分 0
别看长了点，实际单词的查询，'*'只可能在s1或s2中，因此上面对称的那段代码就可以不要了。
QQ:38423320 多交流
mjohh@163.comTop
