题目要求：
写出一个findDNAMatch函数，返回s1链与s2链配对的位置（除findDNAMatch和getC函数以外其他代码已给出）
思路：
用kmp算法解决配对问题
问题：
为什么debugging的时候，运行的到findDNAMatch函数的for循环处直接跳过循环体，返回-1了呢？
#include <iostream>
#include <string>
#include "console.h"
using namespace std;
/* Prototypes */
int findDNAMatch(string s1, string s2, int start = 0);
string matchingStrand(string strand);
void findAllMatches(string s1, string s2);
void getC(string s,int C[]);
/* Main program */
int main() {
findAllMatches("TTGCC", "TAACGGTACGTC");
findAllMatches("TGC", "TAACGGTACGTC");
findAllMatches("CCC", "TAACGGTACGTC");
return 0;
}
/*
* Function: findAllMatches
* Usage: findAllMatches(s1, s2);
* ------------------------------
* Finds all positions at which s1 can bind to s2.
*/
void findAllMatches(string s1, string s2) {
int start = 0;
while (true) {
int index = findDNAMatch(s1, s2, start);
if (index == -1) break;
cout << s1 << " matches " << s2 << " at position " << index << endl;
start = index + 1;
}
if (start == 0) {
cout << s1 << " has no matches in " << s2 << endl;
}
}
/*
* Function: findDNAMatch
* Usage: int pos = findDNAMatch(s1, s2);
* int pos = findDNAMatch(s1, s2, start);
* ---------------------------------------------
* Returns the first index position at which strand s1 would bind to
* the strand s2, or -1 if no such position exists. If the start
* parameter is supplied, the search begins at that index position.
*/
int findDNAMatch(string s1, string s2, int start) {
int C[s1.length()];
int j=-1,i=start-1;
getC(s1,C);
for (;i<s2.length();i++){
while (j>=0&&s2[i+1]+s1[j+1]==149&&s2[i+1]+s1[j+1]==138){
j=C[j]-1;
}
if (s2[i+1]+s1[j+1]==149||s2[i+1]+s1[j+1]==138)
j++;
if (j==s1.length())
return i-s1.length()+2;
}
// [TODO: modify and fill in the code]
return -1;
}
void getC(string s,int C[]){
C[0] = 0;
int j = -1;
for (int i = 0; i < s.length() - 1; i++) {
while (j >= 0 && s[i+1] != s[j+1])
j = C[j] - 1;
if (s[i+1] == s[j+1])
j++;
C[i+1] = j + 1;
}
}