並行串匹配演算法
你好，C的並行方法為擴展並行。即使用第三方C語擴展來實現，現在基於C的並行擴展有openMP、CUDA等，如果需要推薦書發消息給我。補充：你現在的想法跟AMD的差不多，但是實際用途只在部分代碼上有用，具體大的工程實踐還是需要相關人員自己進行並行設計，你可以通過很多書上的並行方法通過自己設計解析軟體把程序代碼分解為openMP代碼並作為預處理代碼。
⑵ 串列演算法和並行演算法有什麼區別 盡可能詳細點
串列演算法是單個處理器的運算並行演算法，是將一個計算任務分攤到多個處理器上並同時運行的計算方法。比如雙核CPU ，從外部看起來是一個CPU，但是內部有兩個運算核心。
⑶ 陳國良的主要成果
先後主持完成了10多項國家863計劃、國家攀登計劃、國家自然基金、教育部博士基金等科研項目。取得了多項被國內外廣泛引用的、達到國際先進水平的科研成果，發表論文100多篇，出版著作7部，譯著5部，參與主編計算機類辭典、詞彙5部，主審、主編計算機類各種教材8部。
獲國家級二等獎以及部、省、院級一等、二等、三等獎共14項。 [1] 陳國良等，《並行計算機體系結構》，高等教育出版社，2002。
[2] 陳國良，《並行計算：結構，演算法，編程》，高等教育出版社，1999。
[3] 陳國良等，《遺傳演算法及其應用》，人民郵電出版社，1996。
[4] 陳國良，《並行演算法的設計與分析》，高等教育出版社，1994。
[5] 陳國良，陳崚，《VLSI計算理論與並行演算法》，中國科大出版社，1991。
[6] 陳國良，《並行演算法：排序和選擇》，中國科大出版社，1990。
[7] 王鼎興，陳國良，《互連網路結構分析》，科學出版社，1990。 陳國良，基於曙光1000的中尺度數值氣象預報系統及其在江淮流域適用性研究，小型微型計算機系統，Vol.21, No.11, p1121-1125, 2000.11。
陳國良，淮河中上游群庫聯合優化調度演算法及其並行實現，小型微型計算機系統，Vol.21, No.6, p603-607, 2000.6。
陳國良，林潔，顧乃傑， 分布式存儲的並行串匹配演算法的設計與分析，軟體學報， 11(6), pp. 771-778, 2000.6
Chen gouliang，Heuristics for Line Capacity Design of PWE Assembly Systems，J. of China Univ. of Sci. & Tech.，Vol.30, No.2, p142-150, 2000.4。
陳國良，桂孝生，楊勃，Walch變換的截斷方法及其並行實現，中國科大學報，Vol.28，No.3，pp.270-276，1998
陳國良，許錦波，LogP模型上的一類蝶式計算的通信策略，計算機學報，Vol.20，No.8，pp.695-701，1997
陳國良，熊焰，顧乃傑，面向應用的神經信息處理系統（NIPS），計算機研究與發展，Vol. 33，No.12，pp.887-892，1996
陳國良，李曉峰，黃偉民，並行FFT演算法在3種並行計算模型上的設計和分析，軟體學報，Vol.7，增刊， pp.57-63，1996
陳國良，並行演算法的可擴放性分析， 小型微型計算機系統，Vol.16，No.2，pp.10-16，1995
陳國良，梁維發，沈鴻，並行圖論演算法研究進展，計算機研究與發展，Vol.32，No.9，pp.1-16，1995
陳國良，更實際的並行計算模型，小型微型計算機系統，Vol.16，No.2，pp.1-9，1995
Chen Guoliang，Zhu Song-chun，Chin Shao-ou，On the Master-Slave Neural Network Models，proc.IJCNN』92，Beijing，1992
陳國良，熊焰，方祥，通用並行神經網路模擬系統GP2N2S2，小型微型計算機系統，Vol.13，No.12，pp.16-21，1992
陳國良，神經計算及其在組合優化中的應用，計算機研究與發展，Vol.29，No.5，pp.1-21，1992
陳國良，朱松純，秦小鷗，主從通用神經網路模型，電子學報，Vol.20，No.10，pp.24-32，1992
陳國良，張永民，改進的多層柵格嵌入演算法，計算機學報，Vol.14，No.5，pp.332-339，1991
陳國良，韓雅華，Benes網路的半自動選路法，計算機學報，Vol.13，No.3，pp.161-173，1990
G.L.Chen，An O(n) Switch setting Algorithm for the Benes Network，PPCC-3，Beijing，China，Vol. 8，pp.16-19，1989
陳國良，VLSI並行計算，計算機工程與應用，No.2， pp.1-35，1989
G.L.Chen，H.Shen，A Bitonic Selection Algorithm on Multiprocessors，J.of comput. Sci.&Tech.，Vol.4，No.4，pp.315-322，1989
陳國良，非數值計算的並行演算法（下），計算機研究與發展，Vol.25，No.12，pp.1-10，1988
Chen Guoliang，A Partitioning Selection Algorithm on Multiprocessors，J.of comput. Sci.&Tech.，Vol.3，No.4，pp.241-250，1988
陳國良，劉峻，多處理器上的分組選擇網路，計算機研究與發展，Vol.25，No.8，pp.1-9，1988
陳國良，王忠良，並行歸並選擇演算法，計算機學報，Vol. 11，No.1，pp.14-21，1988
陳國良，沈鴻，SIMD機器上的雙調選擇演算法，計算機研究與發展， Vol. 25，No.1，pp.1-14，1988
陳國良，沈鴻，雙調選擇網路及其在多處理器上實現的雙調選擇演算法，計算機研究與發展，Vol. 24，No.9，pp.1-10，1987
陳國良，熊焰，兩個不同機種局部區域網路Cnet和Omninet網際互連，小型微型計算機系統，No.2，pp.1-8，1987
K.L.Chen and H.Shang，Bitonic Selection Algorithm on SIMD machine，The Second International conf. On computers and applications，Beijing，China，pp.176-182，1987
陳國良，數據流計算機的互連結構，計算機研究與發展，Vol. 23，No.9，pp.2-10，1986
陳國良，計算機網路互連研究，計算機研究與發展，Vol. 23，No.11，pp.2-10，1986
陳國良，選擇網路的比較研究，中國科大學報，pp.109-120，1985
陳國良，多處理機系統的互連網路，計算機研究與發展，Vol. 28，No.8，pp.30-50，1985
陳國良，計算機網路拓撲（上），計算機研究與發展，Vol. 22，No.10， pp.37-45，1985
陳國良，計算機網路拓撲（下），計算機研究與發展，Vol. 22，No.11， pp.7-15，1985
B.W.Wah and K.L.Chen，A partitioning approach to the design of selection networks， IEEE Trans. On-computers，Vol.c-23，No.3 pp.261-268，1984
陳國良，平衡遞歸選擇演算法，計算機研究與發展，Vol. 21，No.4，pp.7-17，1984
陳國良，並行排序演算法，計算機工程與應用，pp.62-72，1984
B.W.Wah and K.L.Chen，Generalized parallel selection networks，The first International conf. On computers and applications，Beijing，China，pp.406-413，1984
數據流計算機，計算機研究與發展，Vol. 21，No.9，pp.34-46，1984
陳國良，平衡分組選擇網路，計算機研究與發展，Vol. 21，No.11，pp.9-21，1984
個人榮譽
中國科學技術大學軟體學院院長、國家高性能計算中心(合肥)主任陳國良教授，數十年來，他嘔心瀝血，勇攀科技高峰，培養了一大批優秀人才，為我國的科技發展和經濟建設作出了重要貢獻。
中國科學院院士、中國科技大學教授陳國良受聘南京郵電大學兼職教授暨院士學術報告會在學校科學會堂報告廳舉行。副校長張順頤教授主持儀式和報告會。副校長鄭寶玉教授向陳國良教授頒發了兼職教授聘書。受聘後，陳院士將不定期到我校對計算機學科和信息與計算學科的學科建設、教學和科研等工作進行指導。
陳國良院士是我國計算機並行演算法的理論、設計和應用方面傑出的科學家。最早提出並行演算法研究的一系列新觀點和新方法，形成了「並行演算法—並行計算機—並行編程」一體化研究體系。在非數值並行演算法和高性能計算及其應用的研究方面做出了系統的創造性成就和重大貢獻。是全國100名名師之一。陳國良院士受聘我校兼職教授後，將會極大地促進計算機學科和信息與計算學科的發展。
研究成果
上世紀90年代中期，陳國良教授開展了高性能計算及其應用的研究，率先成立了我國第一個國家高性能計算中心，推進了我國該領域的發展；開發了自主版權的國產曙光並行機「用戶開發環境」商用軟體，為推廣國產並行機應用做出了重要貢獻。以陳國良為首席科學家的國家高性能計算中心(合肥)成立10年來，先後承擔了國家863、國家自然科學基金等項目20多項，總經費達4000餘萬元。在國內高校率先開設了並行演算法、並行體系結構等一系列高性能計算方面的專業課，形成了並行演算法類教學體系，推動了我國高性能並行計算學科的研究與發展。
陳國良圖冊
陳國良教授將高性能計算的理論與方法應用於淮河流域的防洪、防污和水環境的治理。他與淮委合作研製開發的國家863重大項目安徽省防災減災智能信息與決策支持系統，在汛期對淮河中上游九大水庫進行防洪調度，他負責研製的淮河流域防洪防污智能調度系統，以削峰、錯峰調度為目標，將氣象數值預報、水情信息的獲取與分析、流域匯流計算與洪水預警預報、水庫的聯合調度等有機結合，在流域防洪調度決策工作中發揮了重要的作用。2003年夏，淮河流域遭受特大洪澇災害。陳國良帶領中國科大師生一行十多人跑到一線現場，為防洪調度決策提供高性能計算支持。為確保計算參數的准確性，他還與淮河水利委員會的技術人員一同到方邱湖、西大壩等防洪重點區域實地考察，提出了洪水演進計算方案，為這一區域的防洪調度工作提供了科學依據。
在陳國良眼裡，教學永遠是第一位的。30多年來，他一直站在教學一線。他培養的30多名博士生中，不少人已經成為學科帶頭人和技術骨幹。1998年，陳國良榮獲安徽省教育系統模範和安徽省模範教師稱號，2003年，獲得首屆國家教學名師獎
人物語錄
亦工亦農：農民出生，在農村長大，對農村情況非常的熟悉。陳老說，雖然自己經歷了很多，做過很多職業，但自己骨子裡卻始終不該農民的本色。至於「工」，則是因為進過軍工廠，當過工人。陳老說自己對工人也有深厚的感情，他覺得工人的感情十分的樸素真摯，人也很容易相處。
陳國良圖冊
亦文亦武：念了大學，還出過國深造，也算得上是一名知識分子。而且自1973年調入中國科學技術大學工作至今就一直在與「文」打交道。「武」方面是因為自己在大學畢業後參軍在軍隊里呆了四五年時間，還到過福建前線。
亦強亦弱：進入大學，先是在電力系學強電，則是「強」，後來轉學的無線電與計算機都是弱電壓，所以稱之為「弱」。
亦硬亦軟：先是研究計算機硬體方面的知識，後來又研究了計算機軟體方面的知識。
亦理亦實：既做理論，又實踐。兩手抓，兩手都硬。
亦中亦西：雖然自己在國內外都沒有取得博士學位，但是研究還是有一定的成就。經常到別的國家的高校進行學術交流，在中西兩方面都有一定成果和影響。
陳老還與在場的所有聽眾分享了他的一些小小故事：學英語發音、教專業英語、在部隊的種種經歷……，他幽默詼諧的語言引來了一陣陣掌聲。他還認真回答了互動環節中同學們的積極提問。
二十四個普通的漢字，堆砌的是陳老不平凡的一生。他的謙和、樸素、認真的品質盡現了大師風范，也是這次講座座無虛席的理由。
個人影響
重獎成果中科院院士陳國良獲得個人一等獎
中科院院士、中國科技大學教授、中國高性能計算機中心（合肥）主任陳國良教授申報的高性能並行計算及其應用項目獲得個人首屆「浪潮高性能計算創新獎」一等獎。陳國良教授及其開創的高性能並行計算及其應用，為推動中國高性能科學計算的發展做出了突出的貢獻。在國際上，使我國的高性能並行演算法達到國際先進水平。
高性能並行計算及其應用形成了並行計算理論--並行演算法設計--並行計算實現--並行計算應用一套完整的學科研究體系，提出了並行機結構--並行演算法--並行編程一體化的研究方法。高性能並行計算及其應用的重要內容涉及一些經典問題的並行演算法研究，如網路與排序演算法、圖論演算法、互聯網路及其路由演算法、VLS布局演算法等，達到了國際領先水平。在國際上，高性能並行計算及其應用，將結構、演算法和編程有機聯系起來，解決了水科學、氣象預報、石油開采鑽探等實際科學工程計算問題，也在國際同行研究中獨具特色。
陳國良圖冊
高性能並行計算及其應用目前在國內許多工程項目中得到廣泛的應用，並取得了非常好的經濟和社會效益。以高性能並行計算及其應用為基礎的國家863重大項目安徽省防災減災智能信息與決策支持系統，這一系統將中尺度數值氣象預報模式的計算結果作為水情預測和群庫優化調度的決策參考依據，在汛期對淮河中上游九大水庫進行防洪調度，取得了顯著的社會和經濟效益。
而淮河流域防洪防污智能調度系統，以削峰、錯峰調度為目標，將氣象數值預報、水情信息的獲取與分析、流域匯流計算與洪水預警預報、水庫的聯合調度等有機結合，其研究結果作為預報的參考依據，在流域防洪調度決策工作中發揮了重要的作用。在戰勝2004年夏季淮河遭受的超過50年一遇的特大洪水中，為政府部門防洪提供了及時有效的數據支持，為防洪決策提供了有力的支持。
眾所周知，淮河流域是一個水患與污患並重的特殊流域，非汛期的防污、控污任務非常艱巨。以陳國良院士的並行計算為基礎，利用計算網格、信息網格等網格計算技術，構建的流域數字化基礎信息平台，開發水資源污染控制系統，為淮河污染治理提供了有力的決策支持。2004年夏，淮河遭受到10年一遇的特大污染，追蹤污水團沿河順流下洩的情況，為提前開閘泄污，消化與稀釋污水團提供了高性能計算支持。
⑷ 《並行演算法的設計與分析》pdf下載在線閱讀，求百度網盤雲資源
《並行演算法的設計與分析》（陳國良）電子書網盤下載免費在線閱讀
資源鏈接：
鏈接：
書名：並行演算法的設計與分析
作者：陳國良
出版年份：2009-8
頁數：813
內容簡介：第3版在修訂版的基礎上進行了大幅度的修訂，新增加3章、重寫3章，改寫8章。《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》系統深入地討論了計算機領域中諸多計算問題的並行演算法的設計和分析方法。在著重介紹各種並行計算模型上的常用和典型的並行演算法的同時，也力圖反映本學科的最新成就、學科前沿和發展趨勢。
全書共分二十章，包括基礎篇4章(緒論、設計技術、前綴計算、排序和選擇網路)，並行演算法篇9章（排序和選擇演算法、分布式演算法、並行搜索、選路演算法、串匹配、表達式求值、上下文無關語言、圖論演算法、計算幾何），數值並行演算法篇3章（矩陣運算、數值計算、快速傅氏變換），理論篇4章（組合搜索、隨機演算法、VLSI計算理論、並行計算理論）。
《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》取材豐富，內容系統深入，可作為高等學校計算機及其他信息類有關專業高年級本科生和研究生的教材，也可供從事計算機科學理論和並行演算法研究的科技人員閱讀參考。
《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》初版曾獲1994年度教育部高等學校優秀教材一等獎和1997年度國家級教學成果二等獎。
⑸ 《數據結構（C語言版）》之「串的模式匹配演算法」
# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# define OK 1
# define ERROR 0
typedef int Status;
//串的定長順序存儲結構
# define MAX_STR_LEN 40
typedef char SString[MAX_STR_LEN + 1];//0號單元存放串的長度
Status StrAssign(SString T,char * chars)//生成一個其值等於chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的個數
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos個字元起長度為len的子串
Status SubString(SString Sub,SString S,int pos,int len)
{
int i;
if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
{
return ERROR;
}
for (i=1; i<=len; ++i)
{
Sub[i] = S[pos+i-1];
}
Sub[0] = len;
return OK;
}
//輸出字元串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函數值並存入數組next
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
//求模式串T的next函數修正值並存入數組nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
if (T[i] != T[j])
{
nextval[i] = j;
}
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}
}
//利用模式串T的next函數求T在主串S中第pos字元之後的位置的KMP演算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
int i = pos,j = 1;
while (i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串為：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串為：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的數組為：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d個字元處首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval數組為：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d個字元處首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的從第5個字元起長度為5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2為:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的輸出結果：
------------------------
主串為：a a a b a a a a b
子串為：a a a a b
子串的next的數組為：0 1 2 3 4
主串和子串在第5個字元處首次匹配
子串的nextval數組為：0 0 0 0 4
主串和子串在第5個字元處首次匹配
求串s1的從第5個字元起長度為5的子串s2:
串s2為:a a a a b
Press any key to continue
------------------------------
*/
⑹ 字元串匹配演算法是怎麼算的
這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ boyermoore演算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 聲明： // 該段代碼只是BoyerMoore(名字也許不準確) 的基本思想，當 // 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。 // 該演算法的本質就是從字元串的右端而不是左端開始比較，這 // 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過 // strlen(sFind)個字元）， 如果最右邊的字元匹配則回溯。比如： // // pain // ^ 這是第一次比較n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 這是第二次比較，好爽呀！ // The rain in SpainThe rain in Spain // // 當然，這樣比較會產生一些問題，比如： // // pain // ^ （圖1） // The rain in SpainThe rain in Spain // // 如果比較到這兒，大家都會看到，只需再向後移到兩個字元 // 就匹配成功了，但如果接下去還按上面的方法跳strlen( sFind)的 // 話，就會錯過一次匹配！！！！！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子 // 串，說明有可能在不移動strlen(sFind) 的跨度就匹配成功，那就 // 人為地給它匹配成功的機會嘛！串一下pain串， 直接讓兩個a對齊 // 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可 // 以直接跨過strlen(sFind)個字元了！ 不知我說明白沒？ // // // 查詢串的長度 int nLenOfFind = lstrlen(sFind); // 被查詢串的長度 int nLenOfSrc = lstrlen(sSrc); // 指向查詢串最後一個字元的指針 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查詢串最後一個字元的指針 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比較過程中要用到的兩個指針 TCHAR * pSrc = sSrc; TCHAR * pFind; // 總不能一直讓它比較到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc <= pEndOfSrc ) { // 每次匹配都是從右向左，這是本演算法的核心。 pFind = pEndOfFind; // 如果比較不成功，被查詢串指針將向右串的字元數 int nMoveRightSrc; // 比較被查詢串的當前字元是否和查詢串的最右邊字 // 符匹配，如果匹配則回溯比較，如果全匹配了，該 // 干什麼，我就不用說了吧？:-) while ( pFind >= sFind ) { // TNND，白廢功夫比了！看看需要向右移動幾個 // 字元吧（如果說從右到左是本演算法的核心，則 // 判斷向右移幾個字元則是本演算法的技巧）。 if ( *pSrc != *pFind ) { // 被查詢串的當前字元是否在查詢串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 沒在，直接移lstrlen(sFind)個字元 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一個！接著向左回溯... pFind --; pSrc --; } // 如果在上面的while循環里每一次比較都匹配了 // 那就對了唄！告訴用戶找到了 if ( pFind < sFind ) return ( pSrc + 1 ); // 沒匹配成功，nMoveRightSrc上面已經算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序運行到這兒肯定是沒指望了！ return NULL; } 行了，函數寫完了，我們可以試一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("沒找到"); } //另外一個 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }
⑺ 並行處理的並行演算法的基本策略
在並行處理技術中所使用的演算法主要遵循三種策略：
1．分而治之法：也就是把多個任務分解到多個處理器或多個計算機中，然後再按照一定的拓撲結構來進行求解。
2．重新排序法：分別採用靜態或動態的指令詞度方式。
3．顯式/隱式並行性結合：顯式指的是並行語言通過編譯形成並行程序，隱式指的是串列語言通過編譯形成並行程序，顯式/隱式並行性結合的關鍵就在於並行編譯，而並行編譯涉及到語句、程序段、進程以及各級程序的並行性。
二、並行性描述定義
利用計算機語言進行並行性描述的時候主要有三種方案：
1．語言擴展方案：也就是利用各種語言的庫函數來進行並行性功能的擴展。
2．編譯制導法：也稱為智能編譯，它是隱式並行策略的體現，主要是由並行編譯系統進行程序表示、控制流的分析、相關分析、優化分析和並行化劃分，由相關分析得到方法庫管理方案，由優化分析得到知識庫管理方案，由並行化劃分得到程序重構，從而形成並行程序。
3．新的語言結構法：這是顯式並行策略的體現。也就是建立一種全新的並行語言的體系，而這種並行語言通過編譯就能直接形成並行程序。
三、並行軟體
並行軟體可分成並行系統軟體和並行應用軟體兩大類，並行系統軟體主要指並行編譯系統和並行操作系統，並行應用軟體主要指各種軟體工具和應用軟體包。在軟體中所牽涉到的程序的並行性主要是指程序的相關性和網路互連兩方面。
1．程序的相關性：程序的相關性主要分為數據相關、控制相關和資源相關三類。
數據相關說明的是語句之間的有序關系，主要有流相關、反相關、輸出相關、I/O相關和求知相關等，這種關系在程序運行前就可以通過分析程序確定下來。數據相關是一種偏序關系，程序中並不是每一對語句的成員都是相關聯的。可以通過分析程序的數據相關，把程序中一些不存在相關性的指令並行地執行，以提高程序運行的速度。
控制相關指的是語句執行次序在運行前不能確定的情況。它一般是由轉移指令引起的，只有在程序執行到一定的語句時才能判斷出語句的相關性。控制相關常使正在開發的並行性中止，為了開發更多的並行性，必須用編譯技術克服控制相關。
而資源相關則與系統進行的工作無關，而與並行事件利用整數部件、浮點部件、寄存器和存儲區等共享資源時發生的沖突有關。軟體的並行性主要是由程序的控制相關和數據相關性決定的。在並行性開發時往往把程序劃分成許多的程序段——顆粒。顆粒的規模也稱為粒度，它是衡量軟體進程所含計算量的尺度，一般用細、中、粗來描述。劃分的粒度越細，各子系統間的通信時延也越低，並行性就越高，但系統開銷也越大。因此，我們在進行程序組合優化的時候應該選擇適當的粒度，並且把通訊時延盡可能放在程序段中進行，還可以通過軟硬體適配和編譯優化的手段來提高程序的並行度。
2．網路互連：將計算機子系統互連在一起或構造多處理機或多計算機時可使用靜態或動態拓撲結構的網路。靜態網路由點一點直接相連而成，這種連接方式在程序執行過程中不會改變，常用來實現集中式系統的子系統之間或分布式系統的多個計算結點之間的固定連接。動態網路是用開關通道實現的，它可動態地改變結構，使之與用戶程序中的通信要求匹配。動態網路包括匯流排、交叉開關和多級網路，常用於共享存儲型多處理機中。在網路上的消息傳遞主要通過尋徑來實現。常見的尋徑方式有存儲轉發尋徑和蟲蝕尋徑等。在存儲轉發網路中以長度固定的包作為信息流的基本單位，每個結點有一個包緩沖區，包從源結點經過一系列中間結點到達目的結點。存儲轉發網路的時延與源和目的之間的距離(段數)成正比。而在新型的計算機系統中採用蟲蝕尋徑，把包進一步分成一些固定長度的片，與結點相連的硬體尋徑器中有片緩沖區。消息從源傳送到目的結點要經過一系列尋徑器。同一個包中所有的片以流水方式順序傳送，不同的包可交替地傳送，但不同包的片不能交叉，以免被送到錯誤的目的地。蟲蝕尋徑的時延幾乎與源和目的之間的距離無關。在尋徑中產生的死鎖問題可以由虛擬通道來解決。虛擬通道是兩個結點間的邏輯鏈，它由源結點的片緩沖區、結點間的物理通道以及接收結點的片緩沖區組成。物理通道由所有的虛擬通道分時地共享。虛擬通道雖然可以避免死鎖，但可能會使每個請求可用的有效通道頻寬降低。因此，在確定虛擬通道數目時，需要對網路吞吐量和通信時延折衷考慮。
四、硬體技術在硬體技術方面主要從處理機、存儲器和流水線三個方面來實現並行。
1．處理機：主要的處理機系列包括CISC、RISC、超標量、VL1W、超流水線、向量以及符號處理機。
傳統的處理機屬於復雜指令系統計算(CISC)結構。指令系統大，指令格式可變，通用寄存器個數較少，基本上使用合一的指令與數據高速緩存，時鍾頻率較低，CPI較高，大多數利用ROM 實現微碼控制CPU，而當今的精簡指令系統計算(RISC)處理機指令格式簡單規范，面向寄存器堆，採用重疊寄存器窗口技術，具有多級Cache，多種流水線結構，強調編譯優化技術，時鍾頻率快，CPI低，大多數用硬連線控制CPU。
CISC或RISC標量處理機都可以採用超標量或向量結構來改善性能。標量處理機在每個周期內只發射一條指令並要求周期只完成從流水線來的一條指令。而在超標量處理機中，使用了多指令流水線，每個周期要發射多條指令並產生多個結果。由於希望程序中有許多的指令級並行性，因此超標量處理機更要依靠優化編譯器去開發並行性。
VL1W 結構是將水平微碼和超標量處理這兩種普遍採用的概念結合起來產生的。典型的超長指令字VL1W 機器指令字長度有數百位。在VLlW 處理機中，多個功能部件是並發工作的，所有的功能部件共享使用公用大型寄存器堆，由功能部件同時執行的各種操作是用VL1W 指令來同步的，每條指令可指定多個操作。VL1W 指令解碼比超標量指令容易，但在開發不同數量的並行性時總是需要不同的指令系統。VL1W 主要是開發標量操作之間的並行性，它的成功與否很大程度取決於代碼壓縮的效率，其結構和任何傳統的通用處理機完全不兼容。即使同一結構的不同實現也不大可能做到彼此二進制兼容。VL1W 的主要優點在於它的硬體結構和指令系統簡單，在科學應用領域可以發揮良好作用，但在一般應用場合可能並不很好用。
向量處理機對數組執行向量指令，每條指令都包含一串重復的操作。它是專門設計用來完成向量運算的協處理機，通常用於多流水線超級計算機中。向量處理機可以利用循環級展開所得的並行性，它可以附屬於任何標量處理機。專用的向量流水線可以在循環控制中消除某些軟體開銷，它的效果與優化編譯器將順序代碼向量化的性能很有關系。從理論上說，向量機可以具有和超標量處理機同樣的性能，因此可以說向量機的並行性與超標量機相同。
符號處理機是為AI應用而研製的，已用於定理證明、模式識別、專家系統、知識工程、文本檢索、科學以及機器智能等許多應用領域。在這些應用中，數據和知識表達式、原語操作、演算法特性、存儲器、I/0和通信以及專用的結構特性與數值計算是不一樣的，符號處理機也稱為邏輯程序設計語言處理機、表處理語言處理機或符號變換器。符號處理並不和數值數據打交道，它處理的是邏輯程序、符號表、對象、劇本、黑板、產生式系統、語義網路、框架以及人工神經網路等問題。這些操作需要專門的指令系統，通常不使用浮點操作。
2．存儲器：存儲設備按容量和存取時間從低到高可分為寄存器、高速緩存、主存儲器、磁碟設備和磁帶機五個層次。較低層存儲設備與較高層的相比，存取速度較快、容量較小，每位元組成本較高、帶寬較寬、傳輸單位較小。
存放在存儲器層次結構中的信息滿足三個重要特性：包含性、一致性和局部性。所謂包含性，指的是一個信息字的復製品可以在比它高的所有層中找到，而如果在高層中丟失了一個信息，則在比它低的所有層中此信息也將丟失。CPU 和高速緩存之間的信息傳送是按字進行的，高速緩存和主存儲器間用塊作為數據傳送的基本單位，主存和磁碟之間又是以頁面為基本單位來傳送信息的，而在磁碟和磁帶機之間的數據傳送則是按文件級處理的。所謂一致性要求的是同一個信息項與後繼存儲器層次上的副本是一致的。也就是說，如果在高速緩存中的一個字被修改過，那麼在所有更高層上該字的副本也必須立即或最後加以修改。為了盡量減少存儲器層次結構的有效存取時間，通常把頻繁使用的信息放在較低層次。維護存儲器層次結構一致性一般有兩種策略，一種是寫直達策略，也就是如果，則立即在所有高層存儲器中進行同樣的修改；另一種是寫回策略，也就是在較低層中對信息進行修改後並不立即在高層存儲器中進行相應的修改，而是等到該信息將被替換或將從低層中消失時才在所有高層存儲器中進行同樣的修改。甚至可以將寫直達和寫回策略的優點結合起來，形成寫一次協議來維護存儲器的一致性。
存儲器的層次結構是在一種程序行為——訪問的局部性基礎上開發出來的。主要有時間局部性、空間局部性和順序局部性。時間局部性指的是最近的訪問項很可能在不久的將來再次被訪問。它往往會引起對最近使用區域的集中訪問。空間局部性表示一種趨勢，指的是一個進程訪問的各項其地址彼此很近。順序局部性指的是在典型程序中，除非是轉移指令，一般指令都是順序執行的。
在多處理機系統中一般使用共享存儲器。對共享存儲器的組織一般採用低位交叉、高位交叉、高低位交叉三種方法。低位交叉又稱並發存取，它是把相鄰的地址放在相鄰的存儲器模塊中，在訪問時不容易產生沖突，並行性較好，但可靠性容錯能力和擴展性均較差。高位交叉又稱允許同時存取，它是把相鄰地址分配到同一個存儲器模塊中，可靠性、容錯能力和擴展性均較強，但訪問時易產生沖突，帶寬較窄，並行性較差。高低位交叉存取又稱C—s存取，它是結合了高位交叉和低位交叉兩種方法的優點，既解決了沖突問題，又能有效地提高容錯能力和並行性，最適合於向量處理機結構。
3．流水線：流水線技術主要有指令流水線技術和運算流水線技術兩種。
指令流水線技術主要目的是要提高計算機的運行效率和吞吐率。它主要通過設置預取指令緩沖區、設置多功能部件、進行內部數據定向、採取適當的指令調度策略來實現。指令調度的策略主要有靜態和動態兩種，靜態詞度是基於軟體的，主要由編譯器完成，動態詞度是基於硬體的，主要是通過硬體技術進行。
運算流水線主要有單功能流水線和多功能流水線兩種。其中多功能流水線又可分為靜態流水線和動態流水線。靜態流水線技術只用來實現確定的功能，而動態流水線可以在不同時間重新組合，實現不同的功能，它除流線連接外，還允許前饋和反饋連接，因此也稱為非線性流水線。這些前饋和反饋連接使得進入流水線的相繼事件的詞度變得很不簡單。由於這些連接，流水線不一定從最後一段輸出。根據不同的數據流動模式，人們可以用同一條流水線求得不同功能的值。
並行計算機發展簡述
40 年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：串列計算時代、並行計算時代。每一個計算時代都從體系結構發展開始，接著是系統軟體（特別是編譯器與操作系統）、應用軟體，最後隨著問題求解環境的發展而達到頂峰。創建和使用並行計算機的主要原因是因為並行計算機是解決單處理器速度瓶頸的最好方法之一。
並行計算機是由一組處理單元組成的，這組處理單元通過相互之間的通信與協作，以更快的速度共同完成一項大規模的計算任務。因此，並行計算機的兩個最主要的組成部分是計算節點和節點間的通信與協作機制。並行計算機體系結構的發展也主要體現在計算節點性能的提高以及節點間通信技術的改進兩方面。
60 年代初期，由於晶體管以及磁芯存儲器的出現，處理單元變得越來越小，存儲器也更加小巧和廉價。這些技術發展的結果導致了並行計算機的出現，這一時期的並行計算機多是規模不大的共享存儲多處理器系統，即所謂大型主機（Mainframe）。IBM360 是這一時期的典型代表。
到了60 年代末期，同一個處理器開始設置多個功能相同的功能單元，流水線技術也出現了。與單純提高時鍾頻率相比，這些並行特性在處理器內部的應用大大提高了並行計算機系統的性能。伊利諾依大學和Burroughs 公司此時開始實施IlliacIV 計劃，研製一台64 個CPU 的SIMD 主機系統，它涉及到硬體技術、體系結構、I/O 設備、操作系統、程序設計語言直至應用程序在內的眾多研究課題。不過，當一台規模大大縮小了的16CPU 系統終於在1975 年面世時，整個計算機界已經發生了巨大變化。
首先是存儲系統概念的革新，提出虛擬存儲和緩存的思想。IBM360/85 系統與360/91是屬於同一系列的兩個機型，360/91 的主頻高於360/85，所選用的內存速度也較快，並且採用了動態調度的指令流水線；但是，360/85 的整體性能卻高於360/91，唯一的原因就是前者採用了緩存技術，而後者則沒有。
其次是半導體存儲器開始代替磁芯存儲器。最初，半導體存儲器只是在某些機器被用作緩存，而CDC7600 則率先全面採用這種體積更小、速度更快、可以直接定址的半導體存儲器，磁芯存儲器從此退出了歷史舞台。與此同時，集成電路也出現了，並迅速應用到了計算機中。元器件技術的這兩大革命性突破，使得IlliacIV 的設計者們在底層硬體以及並行體系結構方面提出的種種改進都大為遜色。
1976 年CRAY-1 問世以後，向量計算機從此牢牢地控制著整個高性能計算機市場15 年。CRAY-1 對所使用的邏輯電路進行了精心的設計，採用了我們如今稱為RISC 的精簡指令集，還引入了向量寄存器，以完成向量運算。這一系列全新技術手段的使用，使CRAY-1 的主頻達到了80MHz。
微處理器隨著機器的字長從4 位、8 位、16 位一直增加到32 位，其性能也隨之顯著提高。正是因為看到了微處理器的這種潛力，卡內基- 梅隆大學開始在當時流行的DECPDP11 小型計算機的基礎上研製成功一台由16 個PDP11/40 處理機通過交叉開關與16 個共享存儲器模塊相連接而成的共享存儲多處理器系統C.mmp。
從80 年代開始，微處理器技術一直在高速前進。稍後又出現了非常適合於SMP 方式的匯流排協議，而伯克利加州大學則對匯流排協議進行了擴展，提出了Cache 一致性問題的處理方案。從此，C.mmp 開創出的共享存儲多處理器之路越走越寬；現在，這種體系結構已經基本上統治了伺服器和桌面工作站市場。
同一時期，基於消息傳遞機制的並行計算機也開始不斷涌現。80 年代中期，加州理工成功地將64 個i8086/i8087 處理器通過超立方體互連結構連結起來。此後，便先後出現了Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及IBM SP 的前身Vulcan 等基於消息傳遞機制的並行計算機。
80 年代末到90 年代初，共享存儲器方式的大規模並行計算機又獲得了新的發展。IBM將大量早期RISC 微處理器通過蝶形互連網路連結起來。人們開始考慮如何才能在實現共享存儲器緩存一致的同時，使系統具有一定的可擴展性（Scalability）。90 年代初期，斯坦福大學提出了DASH 計劃，它通過維護一個保存有每一緩存塊位置信息的目錄結構來實現分布式共享存儲器的緩存一致性。後來，IEEE 在此基礎上提出了緩存一致性協議的標准。
90 年代以來，主要的幾種體系結構開始走向融合。屬於數據並行類型的CM-5 除大量採用商品化的微處理器以外，也允許用戶層的程序傳遞一些簡單的消息；CRAY T3D是一台NUMA 結構的共享存儲型並行計算機，但是它也提供了全局同步機制、消息隊列機制，並採取了一些減少消息傳遞延遲的技術。
隨著商品化微處理器、網路設備的發展，以及MPI/PVM 等並行編程標準的發布，機群架構的並行計算機出現。IBM SP2 系列機群系統就是其中的典型代表。在這些系統中，各個節點採用的都是標準的商品化計算機，它們之間通過高速網路連接起來。
今天，越來越多的並行計算機系統採用商品化的微處理器加上商品化的互連網路構造，這種分布存儲的並行計算機系統稱為機群。國內幾乎所有的高性能計算機廠商都生產這種具有極高性能價格比的高性能計算機，並行計算機就進入了一個新的時代，並行計算的應用達到了前所未有的廣度和深度。
並行計算機隨著微處理晶元的發展，已經進入了一個新時代。目前並行計算機的性能已經突破20PFLOPS，正在向百億億次發展。我國並行計算機的研製已經走在世界前列。2003年由聯想公司生產的深騰6800 在2003 年11 月世界TOP500 排名中位列第14 名，2004 年曙光公司生產的曙光4000A 在2004 年6 月的世界TOP500 排名中位列第10 名，這是我國公開發布的高性能計算機在世界TOP500 中首次進入前十名，這標志著我國在並行計算機系統的研製和生產中已經趕上了國際先進水平，為提高我國的科學研究水平奠定了物質基礎。2013年國際超級計算機大會最新發布的世界超級計算機500強排名中，國防科技大學研製的天河二號超級計算機系統，以峰值計算速度每秒5.49億億次、持續計算速度每秒3.39億億次雙精度浮點運算的優異性能位居榜首。
從TOP500 的前10 名來看，美國仍然是超級計算機的最大擁有者。按照世界TOP500 的統計數據來分析，美國在計算能力上佔有近全世界的一半，在TOP500 中的所有計算機中擁有的數量超過50%。
⑻ 數據結構串匹配十大經典演算法
1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos個字元之後的位置。若不存在，則函數值為0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。
int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函數值求T在主串S中第pos 個字元之後的位置的KMP演算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函數：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next
我現在只有這兩個答案。
⑼ 計算方法中什麼是串列演算法與並行演算法
如果認為題主所說的並行和串列指的GPU和CPU
CPU核心大量晶體管用於緩存，保證盡快執行每一條指令（不管是什麼指令）。
GPU核心大量晶體管用於計算，保證盡量高的指令吞吐量。
可以這樣比喻。
CPU=1個理工科博士（沒有黑文科博士的意思）
GPU=100個小學生
目前的問題是，要算1萬道簡單的加減法，肯定是小學生們一起算的快。
但如果要思考相對論，還是讓博士來吧。
⑽ 串模式匹配演算法（C語言）100分懸賞
第一個樸素演算法:
1.普通的串模式匹配演算法:
int index(char s[],char t[],int pos)
/*查找並返回模式串T在S中從POS開始的位置下標,若T不是S的子串.則返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分別指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //計算主串和模式串的長度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}
第二個KMP演算法.該演算法支持從主串的任意位置開始搜索.
2.KMP演算法:
//求模式串的next函數.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}
//KMP模式匹配演算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函數,求P在主串S中從第POS個字元開始的位置*/
/*若匹配成功.則返回模式串在主串中的位置下標.否則返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];