刪除子串演算法

1. 如下的演算法是從串s中刪除所有與t相同的子串,並返回刪除次數。

1) t[j]
2) j>t[0]
3) n=n+1
4) n

2. c語言字元串刪除

這個用STRING會很方便，string這個容器有功能很強大～～
之所以拋棄char*的字元串而選用C++標准程序庫中的string類，是因為他和前者比較起來，不必 擔心內存是否足夠、字元串長度等等，而且作為一個類出現，他集成的操作函數足以完成我們大多數情況下(甚至是100%)的需要。我們可以用 = 進行賦值操作，== 進行比較，+ 做串聯（是不是很簡單?）。我們盡可以把它看成是C++的基本數據類型。

首先，為了在我們的程序中使用string類型，我們必須包含頭文件 <string>。如下：
#include <string> //注意這里不是string.h string.h是C字元串頭文件

1．聲明一個C++字元串
聲明一個字元串變數很簡單：
string Str;
這樣我們就聲明了一個字元串變數，但既然是一個類，就有構造函數和析構函數。上面的聲明沒有傳入參數，所以就直接使用了string的默認的構造函數，這個函數所作的就是把Str初始化為一個空字元串。String類的構造函數和析構函數如下：
a) string s; //生成一個空字元串s
b) string s(str) //拷貝構造函數 生成str的復製品
c) string s(str,stridx) //將字元串str內"始於位置stridx"的部分當作字元串的初值
d) string s(str,stridx,strlen) //將字元串str內"始於stridx且長度頂多strlen"的部分作為字元串的初值
e) string s(cstr) //將C字元串作為s的初值
f) string s(chars,chars_len) //將C字元串前chars_len個字元作為字元串s的初值。
g) string s(num,c) //生成一個字元串，包含num個c字元
h) string s(beg,end) //以區間beg;end(不包含end)內的字元作為字元串s的初值
i) s.~string() //銷毀所有字元，釋放內存
都很簡單，我就不解釋了。

2．字元串操作函數
這里是C++字元串的重點，我先把各種操作函數羅列出來，不喜歡把所有函數都看完的人可以在這里找自己喜歡的函數，再到後面看他的詳細解釋。
a) =,assign() //賦以新值
b) swap() //交換兩個字元串的內容
c) +=,append(),push_back() //在尾部添加字元
d) insert() //插入字元
e) erase() //刪除字元
f) clear() //刪除全部字元
g) replace() //替換字元
h) + //串聯字元串
i) ==,!=,<,<=,>,>=,compare() //比較字元串
j) size(),length() //返回字元數量
k) max_size() //返回字元的可能最大個數
l) empty() //判斷字元串是否為空
m) capacity() //返回重新分配之前的字元容量
n) reserve() //保留一定量內存以容納一定數量的字元
o) [ ], at() //存取單一字元
p) >>,getline() //從stream讀取某值
q) << //將謀值寫入stream
r) () //將某值賦值為一個C_string
s) c_str() //將內容以C_string返回
t) data() //將內容以字元數組形式返回
u) substr() //返回某個子字元串
v)查找函數
w)begin() end() //提供類似STL的迭代器支持
x) rbegin() rend() //逆向迭代器
y) get_allocator() //返回配置器
下面詳細介紹：

2．1 C++字元串和C字元串的轉換
C ++提供的由C++字元串得到對應的C_string的方法是使用data()、c_str()和()，其中，data()以字元數組的形式返回字元串內容，但並不添加』\0』。c_str()返回一個以『\0』結尾的字元數組，而()則把字元串的內容復制或寫入既有的c_string或 字元數組內。C++字元串並不以』\0』結尾。我的建議是在程序中能使用C++字元串就使用，除非萬不得已不選用c_string。由於只是簡單介紹，詳細介紹掠過，誰想進一步了解使用中的注意事項可以給我留言(到我的收件箱)。我詳細解釋。

2．2 大小和容量函數
一個C++字元 串存在三種大小：a)現有的字元數，函數是size()和length()，他們等效。Empty()用來檢查字元串是否為空。b)max_size() 這個大小是指當前C++字元串最多能包含的字元數，很可能和機器本身的限制或者字元串所在位置連續內存的大小有關系。我們一般情況下不用關心他，應該大小足夠我們用的。但是不夠用的話，會拋出length_error異常c)capacity()重新分配內存之前 string所能包含的最大字元數。這里另一個需要指出的是reserve()函數，這個函數為string重新分配內存。重新分配的大小由其參數決定， 默認參數為0，這時候會對string進行非強制性縮減。

還有必要再重復一下C++字元串和C字元串轉換的問 題，許多人會遇到這樣的問題，自己做的程序要調用別人的函數、類什麼的（比如資料庫連接函數Connect(char*,char*)），但別人的函數參 數用的是char*形式的，而我們知道，c_str()、data()返回的字元數組由該字元串擁有，所以是一種const char*,要想作為上面提及的函數的參數，還必須拷貝到一個char*,而我們的原則是能不使用C字元串就不使用。那麼，這時候我們的處理方式是：如果 此函數對參數(也就是char*)的內容不修改的話，我們可以這樣Connect((char*)UserID.c_str(), (char*)PassWD.c_str()),但是這時候是存在危險的，因為這樣轉換後的字元串其實是可以修改的（有興趣地可以自己試一試），所以我強調除非函數調用的時候不對參數進行修改，否則必須拷貝到一個char*上去。當然，更穩妥的辦法是無論什麼情況都拷貝到一個char*上去。同時我們也祈 禱現在仍然使用C字元串進行編程的高手們（說他們是高手一點兒也不為過，也許在我們還穿開襠褲的時候他們就開始編程了，哈哈…）寫的函數都比較規范，那樣 我們就不必進行強制轉換了。
2．3元素存取

我們可以使用下標操作符[]和函數at()對元素包含的字元進行訪問。但是應該注意的是操作符[]並不檢查索引是否有效（有效索引0~str.length()），如果索引失效，會引起未定義的行為。而at()會檢查，如果使用 at()的時候索引無效，會拋出out_of_range異常。
有一個例外不得不說，const string a;的操作符[]對索引值是a.length()仍然有效，其返回值是』\0』。其他的各種情況，a.length()索引都是無效的。舉例如下：
const string Cstr("const string");
string Str("string");

Str[3]; //ok
Str.at(3); //ok

Str[100]; //未定義的行為
Str.at(100); //throw out_of_range

Str[Str.length()] //未定義行為
Cstr[Cstr.length()] //返回 『\0』
Str.at(Str.length());//throw out_of_range
Cstr.at(Cstr.length()) ////throw out_of_range

我不贊成類似於下面的引用或指針賦值：
char& r=s[2];
char* p= &s[3];
因為一旦發生重新分配，r,p立即失效。避免的方法就是不使用。

2．4比較函數
C ++字元串支持常見的比較操作符（>,>=,<,<=,==,!=），甚至支持string與C-string的比較(如 str<"hello")。在使用>,>=,<,<=這些操作符的時候是根據"當前字元特性"將字元按字典順序進行逐一得 比較。字典排序靠前的字元小，比較的順序是從前向後比較，遇到不相等的字元就按這個位置上的兩個字元的比較結果確定兩個字元串的大小。同時，string ("aaaa") <string(aaaaa)。
另一個功能強大的比較函數是成員函數compare()。他支持多參數處理，支持用索引值和長度定位子串來進行比較。他返回一個整數來表示比較結果，返回值意義如下：0-相等 〉0-大於 <0-小於。舉例如下：
string s("abcd");

s.compare("abcd"); //返回0
s.compare("dcba"); //返回一個小於0的值
s.compare("ab"); //返回大於0的值

s.compare(s); //相等
s.compare(0,2,s,2,2); //用"ab"和"cd"進行比較 小於零
s.compare(1,2,"bcx",2); //用"bc"和"bc"比較。
怎麼樣？功能夠全的吧！什麼？還不能滿足你的胃口？好吧，那等著，後面有更個性化的比較演算法。先給個提示，使用的是STL的比較演算法。什麼？對STL一竅不通？靠，你重修吧！

2．5 更改內容
這在字元串的操作中佔了很大一部分。

首先講賦值，第一個賦值方法當然是使用操作符=，新值可以是string(如：s=ns) 、c_string(如：s="gaint")甚至單一字元（如：s=』j』）。還可以使用成員函數assign()，這個成員函數可以使你更靈活的對字元串賦值。還是舉例說明吧：
s.assign(str); //不說
s.assign(str,1,3);//如果str是"iamangel" 就是把"ama"賦給字元串
s.assign(str,2,string::npos);//把字元串str從索引值2開始到結尾賦給s
s.assign("gaint"); //不說
s.assign("nico",5);//把』n』 『I』 『c』 『o』 『\0』賦給字元串
s.assign(5,』x』);//把五個x賦給字元串
把字元串清空的方法有三個：s="";s.clear();s.erase();(我越來越覺得舉例比說話讓別人容易懂！)。
string提供了很多函數用於插入（insert）、刪除（erase）、替換（replace）、增加字元。
先說增加字元（這里說的增加是在尾巴上），函數有 +=、append()、push_back()。舉例如下：
s+=str;//加個字元串
s+="my name is jiayp";//加個C字元串
s+=』a』;//加個字元

s.append(str);
s.append(str,1,3);//不解釋了 同前面的函數參數assign的解釋
s.append(str,2,string::npos)//不解釋了

s.append("my name is jiayp");
s.append("nico",5);
s.append(5,』x』);

s.push_back(『a』);//這個函數只能增加單個字元 對STL熟悉的理解起來很簡單

也許你需要在string中間的某個位置插入字元串，這時候你可以用insert()函數，這個函數需要你指定一個安插位置的索引，被插入的字元串將放在這個索引的後面。
s.insert(0,"my name");
s.insert(1,str);
這 種形式的insert()函數不支持傳入單個字元，這時的單個字元必須寫成字元串形式(讓人惡心)。既然你覺得惡心，那就不得不繼續讀下面一段話：為了插 入單個字元，insert()函數提供了兩個對插入單個字元操作的重載函數：insert(size_type index,size_type num,chart c)和insert(iterator pos,size_type num,chart c)。其中size_type是無符號整數，iterator是char*,所以，你這么調用insert函數是不行的：insert(0,1, 』j』);這時候第一個參數將轉換成哪一個呢？所以你必須這么寫：insert((string::size_type)0,1,』j』)！第二種形式指 出了使用迭代器安插字元的形式，在後面會提及。順便提一下，string有很多操作是使用STL的迭代器的，他也盡量做得和STL靠近。
刪除函數erase()的形式也有好幾種（真煩！），替換函數replace()也有好幾個。舉例吧：
string s="il8n";
s.replace(1,2,"nternationalizatio");//從索引1開始的2個替換成後面的C_string
s.erase(13);//從索引13開始往後全刪除
s.erase(7,5);//從索引7開始往後刪5個

2．6提取子串和字元串連接
題取子串的函數是：substr(),形式如下：
s.substr();//返回s的全部內容
s.substr(11);//從索引11往後的子串
s.substr(5,6);//從索引5開始6個字元
把兩個字元串結合起來的函數是+。（誰不明白請致電120）

2．7輸入輸出操作
1．>> 從輸入流讀取一個string。
2．<< 把一個string寫入輸出流。
另一個函數就是getline(),他從輸入流讀取一行內容，直到遇到分行符或到了文件尾。

2．8搜索與查找
查找函數很多，功能也很強大，包括了：
find()
rfind()
find_first_of()
find_last_of()
find_first_not_of()
find_last_not_of()
這些函數返回符合搜索條件的字元區間內的第一個字元的索引，沒找到目標就返回npos。所有的函數的參數說明如下：
第一個參數是被搜尋的對象。第二個參數（可有可無）指出string內的搜尋起點索引，第三個參數（可有可無）指出搜尋的字元個數。比較簡單，不多說不理解的可以向我提出，我再仔細的解答。當然，更加強大的STL搜尋在後面會有提及。
最 後再說說npos的含義，string::npos的類型是string::size_type,所以，一旦需要把一個索引與npos相比，這個索引值必須是string::size)type類型的，更多的情況下，我們可以直接把函數和npos進行比較（如：if(s.find("jia")== string::npos)）。

3. 編寫演算法從串s中刪除所有和串t相同的子串

//不但能運行，而且結果還正確

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void DelStr(char *, char *);

int main()
{
char input[256]={0};
char del[20]={0};

printf("請輸入字元串:");
gets(input);

printf("請輸入要刪除的字元串:");
gets(del);

if ( del!=0 )
{
DelStr(input,del);
}

printf("刪除後的結果:%s\n",input);

return 0;
}

void DelStr( char *src, char *dst )
{
char* p=src;
char* q=dst;
int dstLen;

dstLen=strlen(dst);

while( *src!=EOF )
{
if( *q == '\0' )
{
p -= dstLen;
q=dst;//Q重新指向刪除的字元
continue;
}
else if ( *src != *q )
{
q = dst;
}
else
{
++q;
}
*p++ = *src++;//每次都用src來刷新p,如果p指針往回dstLen長度,匹配到的字元串會被覆蓋掉
}
*p='\0';
}

4. 設計一個演算法，刪除串s中從第i個字元開始的連續j個字元，說明演算法所用的存儲結構，並估計演算法的執行時間。

一個循環遍歷S串，在這個循環內另一個循環和T串比較如果相同則標記，在這兩個循環外，可以根據標記刪除S串中T串長度的所有子串。

void str(Sstring S)

{

int i;

for(i=0;ich(i)=S.ch[i];

T->ch[i]='';

T->Length=S.length;

}

void strDelete(Sstring *S,sString T)

{

Sstring temp;

int i,j,flag,k=0;

if(StrLength(*S)>=StrLength(T))

{

for(i=0;i<StrLength(*S);)

{

(4)刪除子串演算法擴展閱讀：

在 ASCII 編碼中，一個英文字母字元存儲需要1個位元組。在 GB 2312 編碼或 GBK 編碼中，一個漢字字元存儲需要2個位元組。在UTF-8編碼中，一個英文字母字元存儲需要1個位元組，一個漢字字元儲存需要3到4個位元組。

在UTF-16編碼中，一個英文字母字元或一個漢字字元存儲都需要2個位元組（Unicode擴展區的一些漢字存儲需要4個位元組）。在UTF-32編碼中，世界上任何字元的存儲都需要4個位元組。

5. （c語言編程）刪除字元串中的子串問題

如果輸入不計時的話你試試這個給你改過的。要盡量避免在循環中的運算表達式……

//#include"stdafx.h"//vc++6.0加上這一行.
#include"stdio.h"
#include"string.h"
intmain(void){
chara[80],b[80];
inti,j,n,t;//m,
gets(a);
gets(b);
n=strlen(a)-strlen(b);
for(i=0;i<n;i++){//n次循環，從a的第n個數開始判斷
for(j=i,t=0;b[t];j++,t++)
if(a[j]!=b[t])
break;
if(!b[t]){
while(a[i++]=a[j++]);
i=-1;
}
}
puts(a);
return0;
}

6. 在JAVA中，如何刪除一個字元串中出現的某個字元。

直接使用空字元串替換就可以了，如下：
String b = "abcabcabc";
b=b.replace("b","");
Java String.replace()方法用法
返回一個新的字元串,用newChar替換此字元串中出現的所有oldChar

7. 1.編寫演算法刪除字元串s中值等於ch的一個字元 2.編寫演算法刪除字元串s中值等於ch的所有字元

//從s中刪除一個字元ch
void delchar(char *s, char ch)
{
while(*s)
{
if(*s == ch) //找到第一個ch
break;
s++;
}
while(*s) //開始刪除
{
*s = *(s+1);
s++;
}
}

//從s中刪除全部ch
void del_chars(char *s, char ch)
{
char *p_read = s;
char *p_write = s;

while(*p_read)
{
if(*p_read != ch) //不為ch的寫入(為ch的跳過)
{
*p_write = *p_read;
p_write++;
}
p_read++;
}
*p_write = 0; //最後補\0
}

8. c語言 字元串刪除子串，一堆[],()中刪除[],()例 ([[]()])-->([])-->0

我想問一下，你要處理的數據全是[]or（）,還是括弧中有數據，你只是要去掉括弧?還有括弧是否都是配對存在的，
其實這是個演算法問題
如果括弧是同時配對存在的，你可以直接掃描一遍凡事遇到'[',']','(',')'都過濾掉就行了
如果不是配對的話，那就得配對刪除，而你現在用的是雙重循環，運算次數成指數級上升，這就是數據量大了慢的原因，我給你一個空間換時間的方法
int func （str, buf）
char *str; /* 傳入須處理的字元串 */
char *ret_buf; /* 處理後的字元串 */
{
char a = '(';
char b = ')';
char c = '[';
char d = ']';
int i = 0;
int j = 0;
int k = 0;
int str_len = strlen (str);
int chr_a_const[len] = {0};/* 標記每個'('字元在字元串中出現的位置 */
int chr_c_const[len] = {0};/* 標記每個'['字元在字元串中出現的位置 */
int dlt_flag[len] = {0};/* 標記需要刪除的字元的位置 */
char *p = NULL;
p = str;
for (i; i < str_len; i++)/* 標記所有的'('和'['的位置 */
{
if (*p = a)
{
chr_const[j] = i;
j++;
}
else if (*p = c)
{
chr_const[k] = i;
k++;
}
else{}
p++;
}
i = 0;
j = 0;
k = 0;
p = str;
for (i; i < len; i++)/* 標記所有配對待刪除的括弧 */
{
else if (*p = a)
{
dlt_flag[i] = 1;
dlt_flag[chr_a_const[j]] = 1;
j++;
}
else if (*p = d)
{
dlt_flag[i] = 1;
dlt_flag[chr_a_const[k]] = 1;
k++;
}
else{}
p++;
}
i = 0;
j = 0;
for (i; i <= len; i++)/* 去除配對括弧 */
{
if (dlt_flag[i] != 1)
{
ret_buf[j] = *(str + i);
j++;
}
}
ruturn 0;
}
搞定，這個函數在數據大的時候，用效率要高點，我沒編譯，你編譯一樣應該沒問題；
記得給分啊！

9. 假設字元串儲存在帶表頭結點的單鏈表中,編寫刪除串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;
}