子串演算法
⑴ 子串定位
如果不需要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演算法。網路一搜一堆介紹。
構造自動機。這個更復雜些。