匹配问题算法

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，子图按顶点数考虑