“计蒜客”杯程序设计竞赛网络赛 G 易彰彪的一张表（BF字符串匹配）

冷不防 2022-08-21 08:00 146阅读 0赞

“计蒜客”杯程序设计竞赛 网络赛 G 易彰彪的一张表（BF字符串匹配）：http://www.jisuanke.com/minicourse/1410/9197

题面描述：

*   1000ms
 *   32768K

易彰彪最近有点奇怪，一向爱打游戏他最近居然盯着一张全是大小写字母的表在看，好像在找什么东西。他说，这是他女神给他的一张表，他需要回答女神的问题——在忽略大小写（即大写字母和小写字母视为同一字母）的情况下，是否能在表中找到某一连续的字符串（第 i*i* 行的尾部和第 i + 1*i*\+1 行的头部视为相连）。但是英语不好的易彰彪一看到字母就头晕，聪明的你能帮他解决这个问题吗？

输入格式：

输入有多组测试数据。

每组第一行会输入两个整数 n*n* 和 m*m*，分别是表的行数和列数，1 \\leq n, m \\leq 301≤*n*,*m*≤30。

第 22 行到第 n + 1*n*\+1 行，每行输入一个长度为 m*m*的字符串，表示表的内容。

第 n + 2*n*\+2 行输入易彰彪想要在表中找到的字符串。

输出格式：

如果按照题目描述能够在表中找到目标字符串，输出`YES`, 否则输出`NO`。

#### 样例1 ####

输入：

5 5
    yiZha
    nGBia
    oaerg
    htyfj
    awert
    yizhangbiao

输出：

YES

题目大意及分析：

在一张只有大写和小写字母的表上寻找一个字符串，且这样字母表是一排排相连的，但由于数据比较小，直接BF即可。

代码实现：

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    
    using namespace std;
    
    char str[50];
    char s[1000];
    char ms[1000];
    
    int len1,len2;
    
    int search1(char s[],char ms[])
    {
        int i=0;
        int j=0;
        while(i<len1 && j<len2)
        {
            if(s[i]==ms[j] || s[i]-ms[j]==32 ||s[i]-ms[j]==-32)
            {
                ++i;
                ++j;
            }
            else
            {
                i=i-j+1;//回溯关键
                j=0;
            }
        }
        if(j>=len2) return 1;
        else return -1;
    }
    int main()
    {
        int n,m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(str,0,sizeof(str));
            memset(s,0,sizeof(s));
            for(int i=0;i<n;i++)
            {
                cin>>str;
                strcat(s,str);
            }
            cin>>ms;
            len1=strlen(s);
            len2=strlen(ms);
            if(len2>len1)
            {
                cout<<"NO"<<endl;
                continue;
            }
    
            int flag=search1(s,ms);
    
            if(flag!=-1)
                cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        return 0;
    }