首页 > 代码库 > 字符串查找(二分和快排的运用)

字符串查找(二分和快排的运用)

Description
 
现在给你一个字典,再给出几个字符串,让你查找,这些字符串是否在其中。


 

Input
 
第一行是两个整数M,N分别表示字典数和字符串数。
第2至第M+1行,每一行是一个字典。
第M+2至第M+2+N行是徐查找的字符串。
(n<=10,0000, m<=20,0000, 字符串长度不超过10,且均为小写字母)


 

Output
 
共N行,每行表示第i个字符串在不在字典中,用0表示不在,1表示在。


 

Sample Input
 
5 3
acc
cat
multiply
do
will
accept
cat
a


 

Sample Output
 
0
1
0

 

解题思路:


拿到该题,第一个想法就是把每个待查找单词一一跟字典里的单词比较,但是一看数据,n<=10,0000, m<=20,0000,数据这么大,如果一一比较肯定会超时,再看看AC人数,果然不多,看来题目并没有预想的那么容易,得用一些之前学的算法来解题了。回想一下,能够提高查找效率的,二分是最为熟知的,所以我打算用二分来做该题。既然要用二分,就必须得让字典中的单词按照字典序排序。效率高的无非就是快排sort函数了。想到这里,整道题也就迎刃而解了,就是一道先排序后二分的基础题罢了。但是我用G++提交的时候竟然是RE,之后改用C++提交便AC了,这点很不理解,希望哪位大牛能为我解答一下。

 

AC代码:

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#define MAX_NUM 100005
using namespace std;

string dic_1[MAX_NUM * 2], word_1[MAX_NUM * 2];

bool cmp(string a, string b)    // 定义一个比较函数,使其按字典序排序
{
    if(a.compare(b) <= 0)
        return true;
    else
        return false;
}

int main()
{
    int M, N;
    char dic_2[15], word_2[15];
    scanf("%d%d", &M, &N);
    for(int i = 0; i < M; i++)
    {
        scanf("%s", dic_2);
        dic_1[i] = dic_2;     // scanf输入效率要高于cin,所以我用scanf输入字符串,再赋值给string
    }
    for(int i = 0; i < N; i++)
    {
        scanf("%s", word_2);
        word_1[i] = word_2;
    }
    sort(dic_1, dic_1 + M, cmp);  // 进行排序

    for(int i = 0; i < N; i++)
    {
        int low = 0, high = M-1, mid;
        bool isFind = false;
        while(low <= high)     // 二分查找
        {
            mid = (low + high) / 2;
            if(word_1[i].compare(dic_1[mid]) == 0)
            {
                printf("1\n");   // 找到则输出1        
        	       isFind = true;        //确定已经找到
                break;
            }
            if(word_1[i].compare(dic_1[mid]) > 0)
                low = mid + 1;
            if(word_1[i].compare(dic_1[mid]) < 0)
                high = mid - 1;
        }
        if(!isFind)
            printf("0\n");  // 找不到输出0
    }
    return 0;
}