精华内容
下载资源
问答
  • 判断子串

    2016-08-06 11:16:16
    1512: 判断子串 时间限制:1 Sec 内存限制:128 Mbyte 提交:207 解决:40 题目描述 背景:大多数生物的遗传信息是存储在由 A(腺嘌呤)、C(胞嘧啶)、G(鸟嘌呤)、T(胸腺嘧啶)4种碱基构成的DNA序列...
    1512: 判断子串
    时间限制:1 Sec     内存限制:128 Mbyte
    提交:207    解决:40
    题目描述

    背景:大多数生物的遗传信息是存储在由 A(腺嘌呤)、C(胞嘧啶)、G(鸟嘌呤)、T(胸腺嘧啶)4种碱基构成的DNA序列上,碱基的不同排列方式决定了DNA序列不同片段所表达的蛋白酶的结构和功能差异。生物的 DNA 序列包含的碱基数一般非常庞大,通常能达到几个GB,有些甚至能到上百GB。如此长的序列,不可能由一次性测量得到。在目前广泛应用的新一代测序技术中,DNA链被随机打断成小片段,然后对小片段进行测序。给定一个DNA序列,然后给定若干片段,分别判断这些小片段是否为给定DNA序列的子串。若是,则返回1;不是,则返回0。

    输入

    首先第一行是给定的原始DNA序列(不超过100个字符),第二行给出给定若干DNA片段的个数,然后每一行是一个DNA片断。

    输出

    判断这些片断是否是给定DNA序列的子串。若是,则返回1;不是,则返回0。

    样例输入

    ATTTGCAG
    2
    ATTT
    ATG
    

    样例输出

    1
    0
    
    
    
    分析:本题数据量较小,用一般的字符串匹配即可AC
    方法1、c++的string类,有专门判断子串的方法( 时间复杂度O(n*n) )
    方法2、一般的字符串匹配( 时间复杂度O(n*n) ),可使用KMP算法进行匹配( 时间复杂度O(n+m) )
    
    
    AC代码如下:
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        string s,str;
        int cas;
        cin>>s;
        scanf("%d",&cas);
        while(cas--)
        {
            cin >> str;
            if (s.find(str)!= string::npos) cout<<1<<endl;
            else cout<<0<<endl;
        }
        return 0;
    }
    

    
    
    一般的匹配:
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    using namespace std;
    
    int main()
    {
        string str1,str2;
        int n;
        cin>>str1;
        cin>>n;
        while(n--)
        {
            int flag=0;
            cin>>str2;
            int l=str1.length();
            int m=str2.length();
            for(int i=0;i<l;i++)
            {
                int j=0;
                int k=i;
                while(str1[k++]==str2[j])
                {
                    j++;
                }
                if(j==m){
                    flag=1;
                    break;
                }
            }
            cout<<flag<<endl;
        }
        return 0;
    }


    KMP算法匹配:
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    using namespace std;
    const int maxn=1e4;
    
    int pre[maxn];
    
    void compute_preflx(char *p, int m)
    {
        int k = 0;
        pre[0] = 0;
        for(int i = 1; i < m; ++i)
        {
            while(k > 0 && p[k] != p[i])
                k = pre[k-1];
            if(p[k] == p[i])
                k++;
            pre[i] = k;
        }
    }
    
    int kmp(char *p, int m, char *text, int n)
    {
        int flag=0;
        compute_preflx(p,m);
        int q = 0;
        for(int i = 0; i<n; ++i)
        {
            while(q >0 && p[q] != text[i])
                q = pre[q-1];
            if(p[q] == text[i]) q++;
            if(q == m)
            {
                flag=1;
                q = pre[q-1];
            }
        }
        return flag;
    }
    
    
    int main()
    {
        char a[maxn],b[maxn];
        int n;
        cin>>a;
        cin>>n;
        while(n--)
        {
            memset(pre,0,sizeof(pre));
            cin>>b;
            int l=strlen(a);
            int m=strlen(b);
            cout<<kmp(b,m,a,l)<<endl;
        }
        return 0;
    }
    


    
    
    展开全文
  • 主要给大家总结介绍了Python中判断子串存在的性能比较及分析的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Python具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
  • zcmu——1108判断子串

    2018-07-31 12:25:54
    函数strstr()判断子串的函数 返回1 #include&lt;bits/stdc++.h&gt; using namespace std; int main() {  char a[120];  char b[10]="Li";  char c[10]="Ting";  int n,i,j;  int...

    函数strstr()判断子串的函数

    返回1

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
       char a[120];
       char b[10]="Li";
       char c[10]="Ting";
       int n,i,j;
       int count;
       int flag1,flag2,flag3;
       while(cin>>n)
       {
       while(n--)
       {
           count=0;
           flag1=flag2=flag3=0;
           cin>>a;
           if(strstr(a,b)!=0)
           {
               flag1=1;
           }
           if(strstr(a,c)!=0)
           {
               flag2=1;
           }
           for(i=0;a[i]!='\0';i++)
           {
               if(a[i]>='A'&&a[i]<='Z')//有三串
               {
                   count++;
               }
           }
           if(flag1==1&&flag2==1&&count==3)
           {
              cout<<a<<endl;
           }
       }
       }
        return 0;
    }
     

    展开全文
  • 用C++编写判断子串的函数

    千次阅读 2018-06-21 16:49:48
    编写判断子串的函数 编写一个函数: int Strstr(char s1[],char s2[]) ; 如果s2不是s1的字串,返回-1 如果s2是s1的子串,返回其在s1中第一次出现的位置 空串是任何串的子串,且出现位置为0int Strstr(char s1[]...
    编写判断子串的函数
      编写一个函数:
      int Strstr(char s1[],char  s2[]) ;
      如果s2不是s1的字串,返回-1
      如果s2是s1的子串,返回其在s1中第一次出现的位置

      空串是任何串的子串,且出现位置为0


    int Strstr(char s1[],char s2[]){
    int i,j,k;
    if(s2[0]==0) return 0;
    for(i=0;s1[i];i++){
    k=i;
    for(j=0;s2[j];k++,j++){
    if(s1[k]!=s2[j]) break;
    }
    if(s2[j]==0) return i;
    }
    return -1;
    }

    展开全文
  • 判断子串问题

    2018-09-15 15:19:48
    判断s2是否是s1的子串 2.编程分析 从s1字符串的第一个字符开始,依次与s2的字符串的各个字符比较,若均相同,则s2是s1的子串;否则再从s1的下一个字符(第二个字符)开始,依次与s2字符串的各个字符作比较……...

    1.问题描述
    判断s2是否是s1的子串
    2.编程分析
    从s1字符串的第一个字符开始,依次与s2的字符串的各个字符比较,若均相同,则s2是s1的子串;否则再从s1的下一个字符(第二个字符)开始,依次与s2字符串的各个字符作比较…设k1,k2分别为s1串,s2串的长度,那么最后一次应从s1的第k1-k2+1个字符开始(即s1[k1-k2]),依次与s2的各个字符比较,若存在不同字符,则s2肯定不是s1的子串。

    用C语言实现代码如下:

    #include <stdio.h>
    #include <string.h>
    int main()
    {
    	char s1[80],s2[80];
    	int i,j,k,k1,k2,flag;
        printf("输入第一个字符串:");
        gets(s1);
        printf("输入第二个字符串:");
        gets(s2);
        k1=strlen(s1);
        k2=strlen(s2);
        flag=0;
        i=0;
        while(i<k1-k2+1&&!flag)
        {
    		j=0;
            k=i;
            while(s2[j]&&s1[k]==s2[j])
            {
    			j++;
                k++;
            }
            if(s2[j]=='\0')
            {
    			flag=1;
                break;
            }
            i++;
        }
        if(flag==1)
    		printf("%s是%s的子串\n",s2,s1);
        else
    		printf("%s不是%s的子串\n",s2,s1);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • #include <cstdio> #include <...//判断子串出现的次数 int occurNum(string str,string substr) { int i=j=k=sum=0; //k记录每次判断的起始位置 while(i<str.size()) { if(str[i]==...
  • MySQL本身没有判断子串个数的函数。所以我写了一个,以备参考。函数体如下:DELIMITER $$DROPFUNCTION IF EXISTS`test`.`func_get_string_count`$$CREATEFUNCTION`test`.`func_get_string_count`( f_strvarchar(8000...
  • 字符串:判断子串

    千次阅读 2018-04-17 21:17:04
    给定两个数组s和t(只包含小写字母),判断s是否为t删除若干字符后得到的子串。 若单纯判断是否为子串,过程比较简单,只需要设置两个指针。 public boolean isSubsequence(String s, String t) { int is = 0, it ...
  • 例题:判断子串

    2017-02-07 18:36:56
    题目:输入两个字符串,判断一个是否为另一个字符串的子串。 #include #include int main() { char str[100],a[100],temp[100]; int len1,len2,loc,i,j,num = 0; printf("Please input a long string:\n"); ...
  • 编写判断子串的函数

    2018-09-06 13:38:01
    不是子串输出-1 是子串输出位置,空串是任何串的子串输出0   int Strstr(char s1[],char s2[]){ if(s2[0] == 0) return 0; for(int i=0; s1[i]; ++i){ int k=i,j=0; for( ;s2[j];++j,+...
  • 以每一个字符为起点比较是否为子串,若未达子串末尾就出现不相等的字符,则说明不是子串,结束比较,开始下一次枚举比较;若到达末尾未出现不相等的字符,则返回位置 /*果s2不是s1的子串,返回-1 如果s2是s1的子串...
  • 1、使用 in 和 not ...使用这两个成员运算符,可以很让我们很直观清晰的判断一个对象是否在另一个对象中,示例如下:>>>"llo"in"hello,python"True>>>>>>"lol"in"hello,python"False2...
  • 输入两个字符串,验证其中一个串是否为另一个串的子串。 【输入】 输入两个字符串, 每个字符串占一行,长度不超过200且不含空格。 【输出】 若第一个串s1是第二个串s2的子串,则输出(s1) is substring of (s2) ...
  • 第二个问题因为子串内可以交换但却不能中间加入其他字符,先将第一个以第一种方式存入,后将第二个每n个(子串长度)一循环后每次都建立新的数组,新的循环,新的比较。只要有一个字母的个数不同就跳出,代表改子串...
  • 母串与子串 c++ 判断位置 oj pat
  • 判断子串的存在

    2013-09-11 10:15:51
    int search(char *s,char * sub) { char *p,*q; p=s;q=sub; while(*p)//该语句是为了让指针一直移动下去 { ... while((*p==*q)&&(*q))//移动到首字符相等的时候,逐个判断 { p++;q++; }
  • 字符串判断子串

    2012-06-14 15:25:31
    采用顺序结构存储串,编写函数,用于判定s2是否是s1的子串 int search(strtype *s1,strtype *s2,int i) {  if(i>=len(s1))  return 0;  else  {  int k=i,j=0;  while(s1->ch[k]==s2->ch[j] && j  {...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,230
精华内容 2,492
关键字:

判断子串