子串算法

⑴ 子串定位

如果不需要kmp之类的牛逼算法，那么

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
intmain()
{
chars[100],p[100];
intls,lp;
intep;

for(;;){
scanf("%s",s);
scanf("%s",p);
ls=strlen(s);
lp=strlen(p);
ep=ls-lp;
if(ep<0)
puts("0");
else{
inti;
for(i=0;i<ep;++i){
if(strncmp(&s[i],p,lp)==0){
printf("%d
",i+1);
break;
}
}
if(i==ep)
puts("0");
}
}
return0;
}

⑵ 在主字符串中查找子串的KMP算法和字符串中查找字符用KMP算法的c语言代码

/***KMP算法是对蛮力算法的优化，原理很简单。但存在最坏情况，时间复杂度很可能会崩坏到O(m+n)。
* 推荐在高频度数据查找采用优化的Boyer-Moore算法。
*以下为代码
***/
/***首先创建一个ADT，这里给出最简形式，省略部分涉及不到的操作***/
ADT String
{voidStrAssign（SString &T，char*S）//值为S的串T
bool SreEmpty(SString &S) //判断空串
int StrLength(SString &s) //返回长度
void Concat (SString &T,SString&S1,SString &S2)//返回组合的新串
void SubString (SString &Sub,SString &S,int pos, int len)//同串则返回第pos后的串的最初位置，否则为0

}
/***算法部分***/
int KMP(char *T,char *p)
{int n=strlen(T);
int m=strlen(P);
int i,j;
for(i=0;i<n-m;i++)
{j=0;
while(j<m&&T[i+j]==P[j])j++;
if(j==m) return i;
}
return -1}

⑶ c语言求回文子串的个数的高效算法

class Palindrome {
public:
int getLongestPalindrome(string A, int n) {
int max=0,count=0;
for(int i=0;i<n;i++) //i作为回文串的中心
{
for(int j=0;((i-j)>=0)&&((i+j)<n);j++)//若回文串是奇数个，i中心前面有j个,后面有j个
{
if(A[i-j]!=A[i+j])
break;
count=j*2+1;
}
if(max<count)
max=count;
for(int j=0;((i-j)>=0)&&((i+1+j)<n);j++)//若回文串是偶数个，i和i+1是中心，前面有j个,后面有j个
{
if(A[i-j]!=A[i+1+j])
break;
count=j*2+2;
}
if(max<count)
max=count;
}
return max;

}

};

⑷ 如何使用C语言求解最长公共子字符串问题及相关的算法

假定字符串采用堆分配方式，编写一个程序，求两个字符串S和T的一个最长公共子串

本题的思路：
本题要实现的算法扫描两个字符串。其中index指出最长公共子串在s中的序号，length指出最长公共子串的长度

堆分配存储表示如下：
typedef struct{
char *ch;
int length;
}Hstring;

Status MaxComString(Hstring S,Hstring T,int &length){

index=0;
length=0;
i=0;

//令i作为扫描字符串S的指针
while(i<S.length){
j=0;
//令j作为扫描字符串T的指针
while(j<T.length){
if(s.ch[i]==T.ch[j]){
//找一个子串，其在字符串S中的序号为i，长度为length1
length1=i;
for(k=1;S.ch[i+k]==T.ch[j+k];k++)length1++;
if(length1>length){
//将较大长度值赋给index与length
index=i;
length=length1;
}
j=j+length1;//继续扫描字符串T中第j=length1个字符之后的字符
}else{
j++;
}
}//while
i++;
}//while
printf("最长公共子串:");
for(i=0;i<length;i++)printf("%c",S.ch[index+i]);
return OK;
}

⑸ 假设字符串储存在带表头结点的单链表中,编写删除串str从位置i开始长度为k的子串的算法

1判断参数是否合法，合法进行下面操作
2.从头结点遍历到第i个位置，定义一个变量，把第i-1个位置的结点保存下来，取名p1
3.继续遍历到第i+k个结点，把第i+k个结点（即最后要删除的结点）保存下来，取名p2
4将p1的指针域指向p2，即p1->next = p2,如果是c语言的话还要释放不用的结点占用的存储空间,
int delete(LinkList h,int begin,int len){//带都结点
if(head==null) return 0;
if(begin<=0||len<=0) return 0;
if(begin+(len-1)>链表长度) return 0;
Node L= h;
Node p1;//放开始删除位置前面的一个结点
Node p2;放第i+k个结点(头结点记为第零个结点)
int count = 0;//记录遍历的结点个数
while(count<=begin+len){//循环count从0到最后一个要删除的字符后面的一个字符
if(count==begin-1) p1 =L;
if(count==begin+len){ p2=L;break;}
L=L.next;
count++;
}
p1.next = p2;
return 1;
}

⑹ 子串的子串数量的计算方法

ab的子串：a、b、ab和一个空子串共4个即（2+1+1）个，abc的子串：a、 b、 c、 ab、 bc 、abc和一个空子串 共（3+2+1+1）个，
所以若字符串的长度为n,则子串的个数就是[n+(n-1)+.......+1+1]个，software中非空子串的个数就是8+7+....+1=36个。

⑺ C语言的KMB算法中涉及到真子串，请问什么是真子串

没有KMB算法，只有KMP算法。
1、串的定义

串( string)是由零个或多个字符组成的有限序列 记作s=“a1a2…an”其中s为串的名字用成对的双引号括起来的字符序列为串的值但两边的双引号不算串值不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数称为串的长度。

2、空串

不含任何字符的串称为空串它的长度n=0记为s=“”。

3、空格串 含有一个或多个空格的串称为空格串它的长度 是空格的个数。若串中含有空格在计算串长时空格应计入串的长度中如s=“I?mastudent”的长度为13。

4、子串、主串 子串是指串中任意个连续字符组成的子序列而包 含该子串的串称为主串。例如, 串s1=“abcdefg”s2=“fabcdefghxyz”则s1为s2的子 串s2相对于s1为主串。另外空串是任意串的子串任意串是自身的子串。除串本身以外的子串都称为真子串。

⑻ 已知顺序串s="abcd"写出所有子串。编写求其全部子串的算法

void substr(char *s)
{
int i,j,k;
for(i=1;i<=strlen(s);i++)
{
for(j=0;j<strlen(s);j++)
{
for(k=0;k<i;k++)
if(i+j<=strlen(s))
printf("%c",s[j+k]);
if(i+j<=strlen(s))
printf("\n");
}
}
}

⑼ 算法题。在一个字符串中有字符有数字，如"sa43lkjkhk3455kh3445566"找出最长的数字子串

1. 如果只是在算法层面，对于算法研究的话，这个问题貌似没有什么好的算法，只能遍历，取最大值，正如楼上这位兄弟所说。
2.如果是为了用程序实现
2.1可以使用正则表达式。
2.2将所有不为数字的字符全部替换成空格，然后按照空格分割，得到一个数组。找数组里面长度最长的元素即可。
方法 2.2 虽然有些笨，但是直观.

⑽ 字符串中查找子字符串一般用什么算法

朴素算法：子串到目标串中查找，匹配一个字符，后移动一个字符。不匹配从子串头部重新开始匹配。
KMP算法。网络一搜一堆介绍。
构造自动机。这个更复杂些。