matlab numpy dedecms log4j qt webpack pmp教程 jquery循环遍历 jquery查找子元素 mysql当前时间减一天 oracle查看数据库状态 mysql倒序 mysql升序 oracle取第一条数据 map删除指定元素 monkey安装 js对象添加元素 python实例 python下载安装教程 python中pop函数 python抛异常 python做界面 java类型 java8的新特性 java初级 java开发者 java8时间 java写入txt文件 java获取当前线程 java的安装 linux用户 磁盘分区软件 kms神龙版 ae脚本管理器 subscribe 管理文件 屏幕录像专家注册机 txplatform 驱动精灵绿色版 vbs代码
当前位置: 首页 > 学习教程  > 编程语言

C++ 算法提高 字符串匹配

2021/1/28 22:54:55 文章标签:

算法提高 字符串匹配 问题描述   给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个…

算法提高 字符串匹配

问题描述
  给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个字母的大写和小写看作相同的字符。

输入格式
  输入的第一行包含一个字符串S,由大小写英文字母组成。
  第二行包含一个数字,表示大小写敏感的选项,当数字为0时表示大小写不敏感,当数字为1时表示大小写敏感。
  第三行包含一个整数n,表示给出的文字的行数。
  接下来n行,每行包含一个字符串,字符串由大小写英文字母组成,不含空格和其他字符。

输出格式
  输出多行,每行包含一个字符串,按出现的顺序依次给出那些包含了字符串S的行。

样例输入
Hello
1
5
HelloWorld
HiHiHelloHiHi
GrepIsAGreatTool
HELLO
HELLOisNOTHello

样例输出
HelloWorld
HiHiHelloHiHi
HELLOisNOTHello

样例说明
  在上面的样例中,第四个字符串虽然也是Hello,但是大小写不正确。如果将输入的第二行改为0,则第四个字符串应该输出。

评测用例规模与约定
  1<=n<=100,每个字符串的长度不超过100。

代码

1.BF解法

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;


int bf(string s,int switch1,string text[],int n)
{
    int len1 = s.length();
    //复制输入的n个字符串,用于输出
    string text2[n];
    for(int i=0;i<n;i++)
        text2[i]=text[i];
    //bf
    for(int i=0;i<n;i++)
    {
        if(switch1==0)
            transform(text[i].begin(),text[i].end(),text[i].begin(),::toupper);
        int x=0,y=0;
        int len2 = text[i].length();
        while(x<len1&&y<len2)
        {
            if(x==-1||s[x]==text[i][y])
                x++,y++;
            else
            {
                y=y-x+1;
                x=0;
            }
        }
        if(x==len1)
            cout<<text2[i]<<endl;
    }
    return 0;
}

int main()
{
    int switch1,n;
    string s;
    cin>>s>>switch1>>n;
    if(switch1==0)
        transform(s.begin(),s.end(),s.begin(),::toupper);
    string text[n];
    for(int i=0;i<n;i++)
        cin>>text[i];
    bf(s,switch1,text,n);
    return 0;
}

2. KMP解法

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;


int kmp(string s,int switch1,string text[],int n)
{
    int len1 = s.length();
    //建立kmp算法中的next数组
    int next[len1];
    int j=0,k=-1;
    next[0]=-1;
    while(j<len1-1)
    {
        if(k==-1||s[j]==s[k])
        {
            k++,j++;
            next[j]=k;
        }
        else
            k = next[k];
    }
    //复制输入的n个字符串,用于输出
    string text2[n];
    for(int i=0;i<n;i++)
        text2[i]=text[i];
    //kmp
    for(int i=0;i<n;i++)
    {
        if(switch1==0)
            transform(text[i].begin(),text[i].end(),text[i].begin(),::toupper);
        int x=0,y=0;
        int len2 = text[i].length();
        while(x<len1&&y<len2)
        {
            if(x==-1||s[x]==text[i][y])
                x++,y++;
            else
                x=next[x];
        }
        if(x==len1)
            cout<<text2[i]<<endl;
    }
    return 0;
}

int main()
{
    int switch1,n;
    string s;
    cin>>s>>switch1>>n;
    if(switch1==0)
        transform(s.begin(),s.end(),s.begin(),::toupper);
    string text[n];
    for(int i=0;i<n;i++)
        cin>>text[i];
    kmp(s,switch1,text,n);
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_650106.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?