精华内容
下载资源
问答
  • 串的模式匹配PTA

    2020-03-26 12:13:49
    给定两个由英文字母组成字符 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现位置,并将此位置后 String 子串输出。如果找不到,则输出“Not Found”。 输入样例: abcabcabcabcacabxy 3 ...

    题目

    给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。

    输入样例:

    abcabcabcabcacabxy
    3
    abcabcacab
    cabcabcd
    abcabcabcabcacabxyz

    输出样例:

    abcabcacabxy
    Not Found
    Not Found

    #include <iostream>
    using namespace std;
    void getNext(string p, int next[])
    {
        int pn = p.size();
        next[0] = -1;
        int k = -1;
        int j = 0;
    
        while (j < pn - 1)
        {
            //p[k]是前缀的字母 p[j]是后缀的字母
            if (k == -1 || p[j] == p[k])
            {
                //先自加 因为是向后移一位
                k++;
                j++;
                //如果p[j] == p[k]
                //那么p[j]失配 p[k]必然也是失配的
                //如果不能出现 p[j] = p[ next[j ]]
                //所以当出现时需要继续递归,k = next[k] = next[next[k]]
                if (p[j] != p[k])
                    next[j] = k;
                else
                    next[j] = next[k];
            }
            else
            {
                k = next[k];
            }
        }
    }
    //KMP不像暴力算法那样失配p就从头开始
    //而是让模式串尽量地移动到有效的位置
    int KMP(string s, string p, int next[])
    {
        int sn = s.size();
        int pn = p.size();
        int i = 0;
        int j = 0;
    
        while (i < sn && j < pn)
        {
            // j == -1 说明p是刚开始匹配
            if (j == -1 || s[i] == p[j])
            {
                i++;
                j++;
            }
            //当前字符匹配失败
            else
            {
                j = next[j];
            }
        }
        if (j == pn)
            return i - j;
        else
            return -1;
    }
    int work(string s, string p)
    {
        int sn = s.size();
        int pn = p.size();
    
        int i = 0;
        int j = 0;
        while (i < sn && j < pn)
        {
            if (s[i] == p[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == pn)
            return i - j;
        else
            return -1;
    }
    int main()
    {
        string s;
        string p;
        cin >> s;
        int n;
        cin >> n;
        while (n--)
        {
            cin >> p;
            int np = p.size();
            int next[np];
            getNext(p, next);
            int index = KMP(s, p, next);
            // cout << index << endl;
            if (index != -1)
                cout << s.substr(index) << endl;
            else
                cout << "Not Found\n";
        }
        return 0;
    }
    
    
    展开全文
  • 串的模式匹配(PTA)

    千次阅读 2019-06-03 18:56:44
    给定两个由英文字母组成字符 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现位置,并将此位置后 String 子串输出。如果找不到,则输出“Not Found”。 本题旨在测试各种不同的匹配算法在...

    给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。

    本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下:

    • 数据0:小规模字符串,测试基本正确性;
    • 数据1:随机数据,String 长度为 10​5​​,Pattern 长度为 10;
    • 数据2:随机数据,String 长度为 10​5​​,Pattern 长度为 10​2​​;
    • 数据3:随机数据,String 长度为 10​5​​,Pattern 长度为 10​3​​;
    • 数据4:随机数据,String 长度为 10​5​​,Pattern 长度为 10​4​​;
    • 数据5:String 长度为 10​6​​,Pattern 长度为 10​5​​;测试尾字符不匹配的情形;
    • 数据6:String 长度为 10​6​​,Pattern 长度为 10​5​​;测试首字符不匹配的情形。

    输入格式:

    输入第一行给出 String,为由英文字母组成的、长度不超过 10​6​​ 的字符串。第二行给出一个正整数 N(≤10),为待匹配的模式串的个数。随后 N 行,每行给出一个 Pattern,为由英文字母组成的、长度不超过 10​5​​ 的字符串。每个字符串都非空,以回车结束。

    输出格式:

    对每个 Pattern,按照题面要求输出匹配结果。

    输入样例:

    abcabcabcabcacabxy
    3
    abcabcacab
    cabcabcd
    abcabcabcabcacabxyz
    

    输出样例:

    abcabcacabxy
    Not Found
    Not Found

     

    用C语言写的,上课老师有讲用strstr(),但是一下子没有写出来,就在这里记录下。

     

     

    参考代码如下:

    #include <stdio.h>
    #include <string.h>
    
    int main(void){
    	char *p;
    	int N, i = 0;
    	char s[1000001], l[100001];
    	scanf("%s", s);
    	scanf("%d", &N);
    	while(i < N){
    		scanf("%s", l);
    		p = strstr(s, l);
    		if(i != N-1){
    			if(p)
    				printf("%s\n", p);
    			else
    				printf("Not Found\n");
    		}
    		else{
    			if(p)
    				printf("%s", p);
    			else
    				printf("Not Found");			
    		}
    		i++;
    	}
    	return 0;
    }

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • PTA 串的模式匹配

    2019-11-07 18:32:52
    给定两个由英文字母组成字符 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现位置,并将此位置后 String 子串输出。如果找不到,则输出“Not Found”。 本题旨在测试各种不同的匹配算法在...

    给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。

    本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下:

    数据0:小规模字符串,测试基本正确性;
    数据1:随机数据,String 长度为 10​5​​,Pattern 长度为 10;
    数据2:随机数据,String 长度为 10​5​​,Pattern 长度为 10​2​​;
    数据3:随机数据,String 长度为 10​5​​,Pattern 长度为 10​3​​;
    数据4:随机数据,String 长度为 10​5​​,Pattern 长度为 10​4​​;
    数据5:String 长度为 10​6​​,Pattern 长度为 10​5​​;测试尾字符不匹配的情形;
    数据6:String 长度为 10​6​​,Pattern 长度为 10​5​​;测试首字符不匹配的情形。
    

    输入格式:

    输入第一行给出 String,为由英文字母组成的、长度不超过 10​6​​ 的字符串。第二行给出一个正整数 N(≤10),为待匹配的模式串的个数。随后 N 行,每行给出一个 Pattern,为由英文字母组成的、长度不超过 10​5​​ 的字符串。每个字符串都非空,以回车结束。
    输出格式:

    对每个 Pattern,按照题面要求输出匹配结果。
    输入样例:

    abcabcabcabcacabxy
    3
    abcabcacab
    cabcabcd
    abcabcabcabcacabxyz
    

    输出样例:

    abcabcacabxy
    Not Found
    Not Found
    
    #include <bits/stdc++.h>
    using namespace std;
    #define N 100005
    
    
    void get_next(string str,int *next){
        int i=0,j=-1;                      
        next[0]=-1;
        int a=str.size();
        while(i<a){                         
            if(j==-1||str[i]==str[j]){      
                i++;j++;
                if(str[i]!=str[j])          //优化
                    next[i]=j;
                else
                    next[i]=next[j];
                //next[i]=j;
            }
            else
                j=next[j];
        }
    }
    int kmp(string strA,string strB,int* next){
        int i=-1,j=-1;
        int a=strA.size(),b=strB.size();
        while(i<a && j<b){
            if(j==-1 || strA[i]==strB[j]){
                i++;j++;
            }
            else
                j=next[j];
        }
        if(j>=b)  return i-b;           //匹配成功返回位置
        else    return -1;
    }
    int main()
    {
        string strA,strB;
        cin>>strA;
        int n;
        cin>>n;
        int next[N];
        while(n--){
            cin>>strB;
            get_next(strB,next);
            int pos=kmp(strA,strB,next);
            int a=strA.size();
            if(pos!=-1){
                for(int i=pos; i<a; i++)
                    cout<<strA[i];
                cout<<endl;
            }
            else
                cout<<"Not Found"<<endl;
        }
    }
    
    
    
    展开全文
  • PTA题目 串的模式匹配

    2020-04-03 12:09:02
    问题描述: 给定两个由英文字母组成字符 ...本题旨在测试各种不同的匹配算法在各种数据情况下表现。各组测试数据特点如下: 数据0:小规模字符,测试基本正确性; 数据1:随机数据,String 长度为 10^​5,P...

    问题描述:

    给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。

    本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下:

    数据0:小规模字符串,测试基本正确性;
    数据1:随机数据,String 长度为 10^​5,Pattern 长度为 10;
    数据2:随机数据,String 长度为 10^​​5 ,
    Pattern 长度为 10^2;
    数据3:随机数据,String 长度为 10^​5,
    Pattern 长度为 10^​3 ;
    数据4:随机数据,String 长度为 10^​5,
    ​​ Pattern 长度为 10^4;
    数据5:String 长度为 10^​6,
    ​​ Pattern 长度为 10^5,
    测试尾字符不匹配的情形;
    数据6:String 长度为 10^6,
    ​​ Pattern 长度为 10^5,
    ​​ 测试首字符不匹配的情形。

    输入格式:

    输入第一行给出 String,为由英文字母组成的、长度不超过 10^​6的字符串。第二行给出一个正整数 N(≤10),为待匹配的模式串的个数。随后 N 行,每行给出一个 Pattern,为由英文字母组成的、长度
    不超过 10^5的字符串。每个字符串都非空,以回车结束。

    输出格式:

    对每个 Pattern,按照题面要求输出匹配结果。

    输入样例:

    abcabcabcabcacabxy
    3
    abcabcacab
    cabcabcd
    abcabcabcabcacabxyz
    

    输出样例:

    abcabcacabxy
    Not Found
    Not Found
    

    试题分析:

    这题目的中,我们可以引用C的库函数strstr(string1,string2) 。该函数用于判断字符串str2是否是str1的子串。如果是,则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串;否则,返回NULL。

    注意:
    功能:strstr返回一个指针,指向string2在string1中首次出现的位置。
    返回类型:字符串类型
    传入参数:参数一、参数二都是字符串类型
    分析:由于strstr函数返回的是一个字符串,而且是一个指针,所以我们需要用一个char类型的指针来接收该函数的返回值,比如 char *p; p=strstr(String1,String2);

    实例代码:

    #include<iostream>
    #include<cstdio> 
    #include<cstring>
    using namespace std;
    int main(){
    	char String[1000001];
    	cin>>String;
    	int N;
    	cin>>N;
    	char Pattern[10][100001];                  
    	char *p;                                   //定义一个char类型的指针,来接收strstr()的结果 
    	for(int i=0;i<N;i++){
    		cin>>Pattern[i];
    	}
    	string  Output[10];                        //用来接收结果,以供输出
    	//错误示范:char Output[10][100001];       //这里一定要用string的数组,否则赋值“Not Found”的时候赋值不上,因为Not Found是一个固定长度的字符串,不能复制到char类型的数组 
    	for(int i=0;i<N;i++){
    		p=strstr(String,Pattern[i]);
    		if(p==NULL){
    			Output[i]="Not Found";
    		}
    		else{
    			Output[i]=p;
    		}
    	}
    	for(int j=0;j<N;j++){
    		cout<<Output[j]<<endl;
    	}
    	return 0;
    }
    

    本期分享到这里就结束啦,大家如果对小编的代码有疑问或者想要小编做其他的程序,都欢迎来私信小编呀!

    展开全文
  • 串的模式匹配 源代码 ///串的模式匹配 ///KMP算法 #include<iostream> #include<cstring> using namespace std; typedef int Position; const int N=1e6+1; const int M=1e5+1; Position KMP(char* ...
  • 7-3 串的模式匹配 (10分) 给定一个主串S(长度<=106)和一个模式T(长度<=105),要求在主串S中找出与模式T相匹配的子串,返回相匹配的子串中的第一个字符在主串S中出现的位置。 输入格式: 输入有两行: 第一...
  • 7-1 串的模式匹配 (30 分) 给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。 本题旨在...
  • PTA 7-4 串的模式匹配 (25 分)

    千次阅读 2019-05-31 15:34:57
    给定两个由英文字母组成字符 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现位置,并将此位置后 String 子串输出。如果找不到,则输出“Not Found”。 本题旨在测试各种不同的匹配算法在...
  • PTA KMP 串的模式匹配 (25 分)

    千次阅读 2019-03-10 18:48:46
    #include &lt;bits/stdc++.h&gt; using namespace std; typedef int Pos; #define NotFound -1 ...void BuildMatch(char *pattern, int *match);...Pos KMP(char *str, char *pattern);... #ifdef ONLINE_JU...
  • KMP 串的模式匹配

    2020-05-24 16:04:36
    来自:PTA_数据结构_KMP 串的模式匹配 给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。...
  • 本题要求实现一个函数BF(string s, string t),求出模式串t在主s中第一次出现位置(从0开始计算),如果在s中找不到t,则输出-1。 函数接口定义: /* s为主,t为模式串。 * 函数返回t在s中第一次出现位置。...
  • 本题使用了KMP匹配模式串算法 输入格式: 每个输入包含 1 个测试用例,即一个不超过 1000 位正整数 N。 输出格式: 对 N 中每一种不同个位数字,以 D:M 格式在一行中输出该位数字 D 及其在 N 中出现次数 M...
  • 1.假设模式是abababaab,则KMP模式匹配算法中next[j] = 0 1 1 2 3 4 5 6 2。 T F 选择题 1.在用KMP算法进行模式匹配时,模式“ababaaababaa”next数组值为____。 选项 A -1,0,1,2,3,4...
  • 文章目录第一章——褚论第二章——线性表第三章——栈与队列第四章——字符判断题单选题 第一章——褚论 ...假设模式是abababaab,则KMP模式匹配算法中next[j] = 0 1 1 2 3 4 5 6 2。 next
  • PTA 数据结构部分判断题

    万次阅读 2018-05-12 21:53:37
    (1分)T FKMP算法的特点是在模式匹配时指示主串的指针不会变小回溯。 (2分)T F对N个记录进行简单选择排序,比较次数和移动次数分别为O(N​2​​)和O(N)。(1分)T F对N个记录进行简单选择排序,比较次...

空空如也

空空如也

1 2
收藏数 24
精华内容 9
关键字:

串的模式匹配pta