Problem Description
有n个小朋友,每个小朋友手里有一些糖块,现在这些小朋友排成一排,编号是由1到n。现在给出m个数,能不能唯一的确
定一对值l和r(l <= r),使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数?Input
首先输入一个整数n,代表有n个小朋友。下一行输入n个数,分别代表每个小朋友手里糖的数量。之后再输入一个整数m,
代表下面有m个数。下一行输入这m个数。Output如果能唯一的确定一对l,r的值,那么输出这两个值,否则输出-1Sample Input
5
1 2 3 4 5
3
2 3 4
Sample Output
2 4
这个题是KMP的应用,需要注意的地方是唯一确定一对值意味着要求模式串在主串中只存在一次!我就是在这里错的。
正确代码:
#include
#include
using namespace std;
const int MAX = 100;
void Get_nextval (string T, int* nextval)
{int l = T.length();nextval[0] = -1;int i = 0, j = -1;while (i < l - 1){if (j == -1 || T[i] == T[j])//j == -1表示没有前后相同的字串,此时回到模式串开头{i++;j++;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}elsej = nextval[j];}
}
int Index (string S, string T, int pos)
{int i = pos, j = 0;int ls = S.length();int lt = T.length();//生成辅助数组int* nextval = new int [lt];Get_nextval(T, nextval);while (i < ls && j < lt){if (j == -1 || S[i] == T[j]){i++;j++;}else{j = nextval[j];}}if (j >= lt)return i-lt;elsereturn -1;
}
int main()
{string s1, s2;int n, m;cin >> n;int temp;for (int i = 0; i < n; i++){cin >> temp;s1 += (char) temp;}cin >> m;for (int i = 0; i < m; i++){cin >> temp;s2 += (char) temp;}temp = Index(s1, s2, 0);//先从下标为0处开始。if (temp <= 0)cout << "-1" << endl;//模式串和主串不匹配else{int i = Index(s1, s2, temp + 1);//再从匹配一次的下标的后一位开始匹配,如果匹配成功,说明不唯一;如果失败,说明唯一if (i >= 0)cout << "-1" << endl;elsecout << temp + 1 << " " << temp + m << endl;}
}
错误代码1:
#include
#include
using namespace std;
const int MAX = 100;
void Get_nextval (string T, int* nextval)
{int l = T.length();nextval[0] = -1;int i = 0, j = -1;while (i < l - 1){if (j == -1 || T[i] == T[j])//j == -1表示没有前后相同的字串,此时回到模式串开头{i++;j++;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}elsej = nextval[j];}
}
int Index (string S, string T, int pos)
{int i = pos, j = 0;int ls = S.length();int lt = T.length();//生成辅助数组int* nextval = new int [lt];Get_nextval(T, nextval);while (i < ls && j < lt){if (j == -1 || S[i] == T[j]){i++;j++;}else{j = nextval[j];}}if (j >= lt)return i-lt;elsereturn -1;
}
int main()
{string s1, s2;int n, m;cin >> n;int temp;for (int i = 0; i < n; i++){cin >> temp;s1 += (char) temp;}cin >> m;for (int i = 0; i < m; i++){cin >> temp;s2 += (char) temp;}temp = Index(s1, s2, 0);if (temp >= 0)cout << temp + 1 << " " << temp + m << endl;elsecout << "-1" << endl;
}
原因:只进行了一次匹配,没有注意到唯一这个要求
错误代码2:
#include
#include
using namespace std;
const int MAX = 100;
void Get_nextval (string T, int* nextval)
{int l = T.length();nextval[0] = -1;int i = 0, j = -1;while (i < l - 1){if (j == -1 || T[i] == T[j])//j == -1表示没有前后相同的字串,此时回到模式串开头{i++;j++;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}elsej = nextval[j];}
}
int Index (string S, string T, int pos)
{int i = pos, j = 0;int ls = S.length();int lt = T.length();//生成辅助数组int* nextval = new int [lt];Get_nextval(T, nextval);while (i < ls && j < lt){if (j == -1 || S[i] == T[j]){i++;j++;}else{j = nextval[j];}}if (j >= lt)return i-lt;elsereturn -1;
}
int main()
{string s1, s2;int n, m;cin >> n;int temp;for (int i = 0; i < n; i++){cin >> temp;s1 += (char) temp;}cin >> m;for (int i = 0; i < m; i++){cin >> temp;s2 += (char) temp;}temp = Index(s1, s2, 0);if (temp <= 0)cout << "-1" << endl;else{int i = Index(s1, s2, temp + m);//错因见下面if (i >= 0)cout << "-1" << endl;elsecout << temp + 1 << " " << temp + m << endl;}
}
错误原因:这里从匹配的下标加上模式串长度处开始
例如:主串1 2 3 2 3 2, 模式串 2 3 2
按照上面代码,第一次匹配到的下标是2,第二次匹配从下标5开始找,不存在第二个和模式串匹配的
但是按照题目来的话,存在两组l,r满足要求,分别是2,4以及4,6。










