【洛谷】 P3879 [TJOI2010]阅读理解

0.总结

Get to the points first. The article comes from LawsonAbs!

• trie树
• 二维数组隐式越界坑

1.题意

判断一个单词是否出现在某串文本中。如果出现，则输出文本的序号【按照从小到大的方式】，否则直接输出换行。

2.分析

典型的模板题，使用 trie 就可以解决。这里我不再介绍trie树了，简单说一下我的主要解决步骤：

• step 1.使用一个trie 数组用于存储每串文本的结构。由题意知，可以设计一个三维数组 trie[][][] ，其中第一维表示的是第几篇阅读；第二维表示节点个数；第三维表示指向【类同二维的tried数组】
• step 2.依次遍历每个查询字符串，然后输出即可。

3.代码

// Created by lawson on 20-6-21.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxN = 1005; //表示最大的短文数，同时也作为最大的个数
const int maxM = 20000;
int n,m;//n表示短文数
short trie[maxN][maxM][27];// 26个小写字母
int p = 0,cnt = 1,tot = 0;//cnt 表示第几篇短文；
bool endF[maxN][maxN];//结束标志 => 用bool省空间

void build(char in[] ){
    int p = 0;
    for(int i = 0;i<strlen(in);i++){
        int cNum = in[i]-'a';
        if(!trie[cnt][p][cNum]){//如果没有记录
            trie[cnt][p][cNum] = ++tot;
        }
        p = trie[cnt][p][cNum];//更新p的值
    }
    endF[cnt][p] = true;
}

//查询in这个字符串是否在trie树中
bool search(int index,char in[]){
    p = 0;
    for(int i = 0;i<strlen(in);i++){
        int cNum = in[i]-'a';
        if(!trie[index][p][cNum])
            return false;
        else
            p = trie[index][p][cNum];
    }
    if(endF[index][p])
        return true;
    return false;
}

int main(){
    scanf("%d",&n);
    while(cnt<=n){
        tot = 0;//重置为0
        scanf("%d",&m);
        char word[30];//每个字符长20
        for(int i = 1;i<=m;i++){
            scanf("%s",word);//输入每个单词
            build(word);
        }
        cnt++;
    }

    scanf("%d",&m);

    char query[25];//待查询的字符串
    for(int i = 1;i<= m;i++){
        int res[maxN];//存储答案
        cnt = 0;//重置
        scanf("%s",query);
        for(int j = 1;j<=n;j++)
            if(search(j,query))
                res[cnt++] = j;
        //更换输出格式
        for(int j = 0;j<cnt;j++)
            if(j!=cnt-1)    printf("%d ",res[j]);
            else printf("%d",res[j]);

        printf("\n");//输出一个空行
    }
}

4.测试用例

2
1 youare
3 my name is
2
you
you

1
3 you you you
1
you

1
4 you a good person
1
yo

3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
yo
s
o
all
all

5.坑点

• 需要注意数组大小的申请，一般情况下，很难得到一个**“高维数组的越界提示”**，比如说二维数组 arr[10][10]，你如果用 arr[5][20] 依然是可以访问到值！所以一定要注意题目的数据范围大小到底需要一个什么范围的数组！千万别模棱两可。