精华内容
下载资源
问答
  • 判断串T是否为串S的子串,若是返回在主串中的位置 算法思想: {将主串S的第一个字符和串T第一个字符进行比较,【若相等则继续比较后面的字符,(若全部一致则说明字符串T为串S 的子串,且主串S开始比较的第一个元素...

    判断串T是否为串S的子串,若是返回在主串中的位置
    算法思想:
    {将主串S的第一个字符和串T第一个字符进行比较,【若相等则继续比较后面的字符,(若全部一致则说明字符串T为串S 的子串,且主串S开始比较的第一个元素的下标就为子串在主串S 中的位置);(若后续比较不一致则说明此次匹配不成功,返回与串第一个字符比较的开始】;

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    //串的顺序存储定义 
    typedef struct
    {
    	char ch[MAXSIZE];
    	int length; 
    }SString;
    
    //串的初始化 
    void StrAssign(SString&S,char cs[])
    {
    	int i;
    	for(i=0;cs[i]!='\0'&&i<MAXSIZE;i++)
    	S.ch[i]=cs[i];
    	S.length=i;
    }
    
    //串的打印
    void print(SString S)
    {
    	int i;
    	for(i=0;i<S.length;i++)
    	{
    		printf("%c",S.ch[i]);
    	} 
    }
    //串的复制   将串T中的数据拷贝到串S中,使得输出的串S中的数据变成串T中的数据 
    void StrCopy(SString &S,SString T)
    {
    	int i;
    	for(i=0;i<T.length;i++)
    	{
    		S.ch [i]=T.ch[i];
    		S.length=T.length;
    		
    	}
     } 
    //串的连接  将串T连接在串S后面
    int StrCat(SString&S,SString T)
    {
    	int i,flag;
    	if(S.length+T.length<=MAXSIZE)
    	{
    		for(i=S.length;i<S.length+T.length;i++)
    		{
    			S.ch[i]=T.ch[i-S.length];
    		}
    		S.length=S.length+T.length;
    		flag=1;
    	}
    	else if(S.length<MAXSIZE)
    	{
    		for(i=S.length;i<MAXSIZE;i++)
    		{
    			S.ch[i]=T.ch[i-S.length];
    		 } 
    		 S.length=MAXSIZE;
    		 flag=0;
    		
    	}
    	else
    		flag=0;
    	return flag;
     } 
     //串的删除操作  删除一个串中从下标第pos位置起,长度为length的字符 
    int StrDelete(SString &S,int pos,int length)
    {
    	int i;
    	if(pos<0||pos>S.length-length)
    		return 0;
    	else
    	 	for(i=pos+length;i<S.length;i++)
    	 	{
    	 		S.ch[i-length]=S.ch[i];
    		}
    		S.length=S.length-length;
    		return 1;
    		 
    }
    //判断串T是否为串S的子串,若是返回在主串中的位置
    int StrIndex(SString S,int pos1,SString T)
    {
    	int i,j;
    	if(T.length==0)
    		return 0;
    	i=pos1;
    	j=0;
    	while(i<S.length&&j<T.length)
    	{
    		if(S.ch[i]==T.ch[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(j>=T.length)
    	return i-j;
    	else
    	return 0;
     } 
    int main()
    {
    	char str[MAXSIZE];
    	SString S,T;
    	printf("输入串S:\n");	
    	gets(str);
    	StrAssign(S,str);//调用串的初始化函数 
    	printf("输出串S:\n");
    	print(S);
    	printf("\n");
    	printf("输入串T:\n");	
    	gets(str);
    	StrAssign(T,str);
    	printf("输出串T:\n");
    	print(T);
    	printf("\n");
    	
    	int pos1,D;
    	pos1=0;
    	D=StrIndex(S,pos1,T);
    	if(D==0)
    		printf("不为子串\n");
    	else
    	{
    		printf("子串的位置为:%d\n",D);
    	}
    	/*StrCopy(S,T);//调用拷贝函数 
    	printf("拷贝后的串为:\n");
    	print(S);
    	printf("\n");*/
    	//连接函数 
    	StrCat(S,T);//调用连接函数 
    	printf("连接后的串为:\n");
    	print(S);
    	printf("\n");
    	int pos,length;
    	printf("请输入要删除字符开始的下标:\n");
    	scanf("%d",&pos);
    	printf("请输入要删除字符的长度:\n");
    	scanf("%d",&length);
    	StrDelete(S,pos,length);//调用删除函数 
    	print(S);
    	printf("\n");
    	
    }
     
    

    在这里插入图片描述

    展开全文
  • 编写一个程序,判定一个字符串是否是另一个字符串的子串,若是,则返回子串在主串中的位置。要求不能使用系统函数。 #include<iostream> using namespace std; int match(char s[], char p[]) { int i, j, k;...

    .编写一个程序,判定一个字符串是否是另一个字符串的子串,若是,则返回子串在主串中的位置。要求不能使用系统函数。

    #include<iostream>
    using namespace std;
    int match(char s[], char p[])
    {
    	int i, j, k;
    	for (i = 0; s[i] != '\0'; i++)
    	{
    		for (j = i, k = 0; s[j] != '\0' && p[k] == s[j]; j++, k++);
    		if (p[k] == '\0')
    			return i;
    	}
    	return -1;
    }
    
    int main()
    {
    	char s1[100], s2[100];  //创建一个字符数组
    	cout << "请输入字符串A: " << endl;
    	cin.getline(s1, 100);
    	cout << "请输入子字符串B: " << endl;
    	cin.getline(s2, 100);
    	int k = match(s1, s2);
    	if (k != -1)
    		cout << s2 << "是" << s1 << "的子字符串,位置在" << k + 1 << endl;
    	else
    		cout << s2 << "不是" << s1 << "的子字符串";
    	system("pause");
    	return 0;
    }
    
    

    在这里插入图片描述

    展开全文
  • 在做这道题时,设置一个count变量,通过if语句进行判断模式串是否已经完全匹配一次。...sLen) //因为是在主串中匹配个数,所以不能用模式串的长度作为判断循环的条件 { if (j == -1 || s[i] == p[j])

    在做这道题时,设置一个count变量,通过if语句进行判断模式串是否已经完全匹配一次。

    int count_kmp(char *s, char *p,int next[]){
    	int count = 0,i = 0;
    	int j = 0;
    	int sLen = strlen(s);
    	int pLen = strlen(p);
    	while(i<sLen)  //因为是在主串中匹配个数,所以不能用模式串的长度作为判断循环的条件
    	{
    		if (j == -1 || s[i] == p[j])
    		{
    			i++;
    			j++;
    		}else{
    			//如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]    
    			//next[j]即为j所对应的next值  ,最长前后缀相同匹配长度    
    			j=next[j];
    	    }
    	    if(j >pLen-1){ //如果 模式串数组下标大于 数组最大长度的下标 ,则说明模式串 已经全部匹配完毕 
    	    	count++;   // count ++ 
    	    	i--;      // 上面的if 将i+1,如果不减一,下次匹配就会跳过 一个char 
    	    	j = -1;  // 因为模式串已经全部匹配完毕,下次匹配时要从头开始匹配,将j置-1; 
    		}
    	}
    	printf("\n%d",count);
    	return count;
    }
    
    展开全文
  • ①注意求长度时不要每次都算,直接记录下来len=strlen(s); 否则会造成超时 ②求出现的次数就是是否匹配的基础上加上判断 ... //子串回到下一个可以匹配的位置  } ③kmp时注意  if(j==-1...

    ①注意求串长度时不要每次都算,直接记录下来len=strlen(s);

    否则会造成超时

    ②求出现的次数就是在求是否匹配的基础上加上判断

     if(j==len1)
                {
                    ++sum;
                    j=next[j];  //子串回到下一个可以匹配的位置

                }

    ③kmp时注意 

    if(j==-1||s1[j]==s2[i])
                {
                    ++i;++j;
                }

    当j=-1时i,j都要向后挪

    展开全文
  • 最长回文子串

    2020-06-23 19:06:51
    acabacb 我们假设现在遍历到第四个节点b,对他调用寻求回文子串长度的方法,就会对比 3 5位置的元素是否相等 如果相等则aba是一个回文 然后i-2 和i+2位置继续判断 最后得到回文子字符长度返回 ,在主循环添加...
  • 字符的包含

    千次阅读 2016-03-10 16:13:22
    要求:给定一个主串X和子串Y判断主串是否包含子串,包含是指子串中的所用字符均在主串中出现,所谓出现不要求连续,如:主串X:abcdef 子串为:Y:cde,Z:ade,M:adx,则答案为true,true false,要求空间复杂度为O...
  • C/C++描述 LeetCode 459. 重复的子字符 行秒解。

    千次阅读 多人点赞 2020-08-24 14:11:07
    C/C++描述 LeetCode 459....给定一个非空的字符判断是否可以由它的一个子串重复多次构成。给定的字符只含有小写英文字母,并且长度不超过10000。 示例 1: 输入: "abab" 输出: True 解释: 可由
  • bzoj 2806 多个串匹配

    2017-09-14 22:33:23
    多个主串和多个询问串,每次询问将询问串分成多个连续子串,如果一个子串长度>=L且在主串中出现过就是熟悉的 如果熟悉的字符串长度>=询问串长的90%就是熟悉的文章;求成为熟悉的文章的最大的L   主串建广义SAM...
  • 本文详细介绍两种最常见的字符串模式匹配算法:朴素模式匹配KMP模式匹配字符串模式匹配,也称子串的定位操作,通俗的说就是在一个主串中判断是否存在给定的子串(又称模式串),若存在,则返回匹配成功的索引。...
  •  先以主串S第pos个字符为S子串的第一个字符,模式串T的长度作为S子串的长度,得到一个子串去与模式串T的对应字符逐个比较,若子串与模式串相同,则返回S中子串的第一个字符位置,这就是模式串在主串S的位置;...
  • 字符功能实现

    2013-04-29 00:35:54
    复制:复制一个任意长度字符串的值到另外一个任意长度字符串 ... 判断包含:判断一个主串是否包含另外一个子串 */ #include #include #include #define MAX_SIZE 5 #define INCREASE_SIZE 10 using
  • 题目本质让我们求解的是在主串中选出k个不相交的子串。这个子串的最长长度是多少。其实答案具有单调性,二分求解。 我们首先字符串哈希预处理,然后二分答案 判断部分: 用两个哈希表分别记录长度为len的子串位置和...
  • 数据结构:第四章串和队列 4.1串的概念 字符串是由n字符组成的有限序列,串也是种特殊的...在主串中寻找子串的位置成为模式匹配,子串又叫模式串。 next函数 nextvalue函数 kmp算法算法的时间复杂度 主串为m子串
  • 假设有两串S,T,设S为主串,也称正文串,T为子串,也称为模式,在主串S中查找与模式T相匹配的子串,如果查找成功,返回匹配的子串第1字符在主串中的位置。最笨的办法就是穷举所有S的所有子串判断是否与T匹配...
  • 今天主要想总结一下字符串中的一个经常出现于教材的一个经典算法,算法的要求很简单,就是给出两个字符串,判断一个字符串是否是另一个字符串的子串.子串的定位操作通常也叫做模式匹配.算法教材中,我们通常把这两个...
  • 子串的第一个字符在主串中的序号称为子串在主串中的位置。 4.2.2 字符串的存储结构 有三种方法表示字符串的长度 ①在数组最后一个位置(MaxSize-1)存储串长度 ②用数组的0号单元存储串的长度 ③判断当前字符是否为...
  • 字符模式匹配

    2018-04-12 21:03:00
    就是判断主串S中是否存在给定的子串,如果存在,那么返回子串在S的位置,否则返回0。 实现这种操作有两种算法: - 朴素的模式匹配算法 S长度为n,T长度为m。 思路 对于主串的每字符,做长度为strlen(T) 的...
  • 在主串S中查找与模式T相匹配的子串,如果查找成功,返回匹配的子串一个字符在主串中的位置。 //最笨的办法就是穷举所有S的所有子串判断是否与r匹配。该算法称为BF(Brute Force) int BF(stri...
  • 字符串匹配分为两种情况:(1)字符串一对一的匹配,(2)在一个字符串中同时查找多个子串。 1.对于一对一的匹配,有经典的BF算法(Brute Force)暴力匹配算法: 核心思想:字符串匹配算法中有两个核心词:(1)基础...
  • 给定两个字符串A,B,判断T是否为S的子串(变式:寻找子串B串A的位置)。  要求一个O(|A|+|B|)的做法。  通常称A为目标串(或主串),B为模式串。  算法过程:  我们假设串A的长度为n,串B的长度为m,每...
  • 匹配问题与KMP算法

    2018-07-21 17:25:22
     给一个较长的T,长n,和一个较短的P,长m,设计算法判断P中是否包含T,若有,返回T中和P匹配的子串起点的下标。 蛮力算法 最容易想到的就是两个头部对齐,两个指针i、j表示T和P进行匹配的元素的下标...
  • 如果你是电脑前看的这篇文章,... 如果现在给了我们两个字符串,第一个字符串为主串,第二个字符串为子串,我们需要判断子串是否主串的一部分,怎么进行判断?从常规的思维出发,我们很容易想到,同时从主串和子串
  • KMP也是一种模式匹配算法,简单来说就是将子串与主串去匹配,查找子串是否存在与主串中。之前分析过得BF算法,虽然它也是一种简单常用的模式匹配算法,但我们可以发现,BF算法中主串的每一个字符都要和子串第一位...
  • <题目链接> 题目大意: 就是求k个长度为60的字符串的最长连续公共子串,2<=k<...将第一个字串的所有子串枚举出来,然后用KMP快速判断子串是否在所有主串中出现,如果都出现过,那...

空空如也

空空如也

1 2 3 4 5
收藏数 85
精华内容 34
关键字:

判断一个子串是否在主串中