匹配問題演算法

A. C語言數據結構串的模式匹配演算法問題

和while循環裡面的一樣，i指針退回原來的位置並指向下一位，應該是多少？i-j+2是吧！

這里不用指向下一位，直接return它的位置就行了，於是return i-j+1

i-j+1和i-t[0]相等！

B. 字元串匹配演算法是怎麼算的

這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ 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); } }

C. 數據匹配問題

kmp匹配演算法，目的是提取出子串重復信息，防止無用匹配，減少匹配循環次數

D. 數據結構括弧匹配的演算法問題

return0 就是不匹配，return 1 就是匹配，最後判斷棧是不是空的，棧如果是空的，說明匹配了，返回 1 ，如果不是空的，說明還有左括弧，匹配失敗

E. 數據結構 括弧匹配演算法

樓上說的是一個原因，不過去掉!StackEmpty(S)後問題依舊。
你的原因主要是這里：
case ')':{Pop(S,e);
if(e!='(') flag=1; break;}

應該先判斷，再出棧。不能先出棧再判斷。

F. C#括弧匹配問題演算法

constCharRIGHT='}';
constCharLEFT='{';
staticvoidMain(string[]args)
{
Queue<Char>queue=newQueue<Char>();
StringtargetValue="sd{{}";
BooleanisValid=true;

foreach(CharitemintargetValue)
{
if(item.Equals(LEFT))queue.Enqueue(item);

if(queue.Count>0&&!item.Equals(RIGHT)&&!item.Equals(LEFT)){
isValid=false;
break;
}

if(queue.Count>0&&item.Equals(RIGHT))queue.Dequeue();
}

if(isValid&&queue.Count==0)Console.WriteLine("匹配");
elseConsole.WriteLine("不匹配");

Console.ReadKey();
}

G. fp一個匹配問題（匈牙利演算法）

program p1557;
var
i,j,m,n,x,y,tot,v:longint;
link:array[1..200] of longint;
cover,f:array[1..200] of boolean;
map:array[0..200,0..200] of boolean;

Function work(i:longint):boolean;
var
q,k:longint;
begin
work:=true;
for k:=1 to n do
if (map[i,k]=true) and (cover[k]=false) then
begin
q:=link[k];
link[k]:=i;
cover[k]:=true;
if (q=0) or (work(q)=true) then exit;
link[k]:=q;
end;
work:=false;
end;

Begin
assign(input,'i.i'); reset(input);
assign(output,'o.o'); rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=true;
repeat
readln(x,y);
map[y,x]:=false;
until (x=0) and (y=0);
for i:=1 to n do
begin
for j:=1 to n do
cover[j]:=false;
work(i);
end;
tot:=0;
for i:=1 to n do
begin
j:=link[i];
link[i]:=0;
map[j,i]:=false;
for v:=1 to n do cover[v]:=false;
if (work(j)=false) then
begin
tot:=tot+1;
writeln(j,' ',i);
end;
map[j,i]:=true;
link[i]:=j;
end;

if tot=0 then writeln('none')

end.

H. 數據結構 字元串 模式匹配問題 KMP演算法

你的程序本身思路沒有錯，但錯在以下幾點：
1.在程序中有字元串S和T，你用S[0]代表字元串的長度，但S是字元串，S[0]是長度嗎？
2.在main函數中，你輸入的S和T都是用gets(S)或gets(T),那麼它們都是以下標0開頭的，你應該要進行處理，使它以下標1作為開頭（可以這樣gets(&S[1]); 然後S[0] = strlen(&S[1]) + '0';在用S[0]作為長度的時候，把它從字元變成數字就行了)。

I. 數據結構（c++）字元串 模式匹配演算法問題，對高手來說只要寫一點點

恩,網路提問太差了 我都丟了幾次高分都沒有成功!
我估計丟了500分了不是亂答就是沒通過,分又沒有

J. 離散數學的圖論中的二部圖的完全匹配和最大匹配問題怎麼理解

11個互不同構的生成子圖，18個互不同構的子圖
ps:生成子圖按邊數考慮，邊數從0到6，子圖按頂點數考慮