英文:
How to fix 'out of bound' error in my KMP algorithm implementation for a given testcase?
问题
以下是您要翻译的内容：
我刚刚阅读了KMP算法，然后自己编写了算法，对一些测试用例有效，但在给定的测试用例中，编译器报告了一些越界/溢出类型的错误。
测试用例：haystack="mississippi" needle="issipi"。
我检查了lps的输出=0 0 0 1 -1 1，它应该在索引2处打印1，并且-1甚至不应该存在。请告诉我我犯了什么错误？
请注意，我已经删除了代码部分，只返回翻译好的内容。
英文:
i just read the KMP algorithm and then i wrote the algorithm myself, it worked for few testcases but at the given testcase the compiler gave some out of bound/overlfow kind of error.
testcase: haystack="mississippi" needle="issipi".
i checked that the output of lps=0 0 0 1 -1 1 , it should print 1 at index=2 and -1 shouldn't even be there.pls tell what mistake i did?
`string haystack="mississippi";
string needle="issipi";
int n=haystack.length();
int m=needle.length();
if(m>n) cout<<"no occurence";
vector<int> lps(m,-1);
lps[0]=0;
int len=0;
for(int i=1;i<m;i++){
if(needle[i]==needle[len]){
len++;
lps[i]=len;
}
else{
if(len>0) len=lps[len-1];
else lps[i]=0;
}
}
for(auto it:lps){cout<<it<<" ";}
int i=0;
int j=0;
while(i<n && j<m){
if(haystack[i]==needle[j]){
i++;
j++;
if(j==m){
cout<<"occurence at: "<<i-j<<endl;
j=lps[j-1];
}
}
else{
if(j>0) j=lps[j-1];
else i++;
}
}`
答案1
得分: 0
这部分代码的问题似乎出现在以下部分：
while (i < n && j < m) {
if (haystack[i] == needle[j]) {
i++;
j++;
if (j == m) {
cout << "occurence at: " << i - j << endl;
j = lps[j - 1];
}
}
else {
if (j > 0) j = lps[j - 1];
else i++;
}
在while循环迭代中，当i = 9时，执行了j = lps[j - 1]这一行代码。由于在这个循环迭代中j = 5，所以j被设置为lps中索引为5的值，即-1。在下一次循环迭代中，代码尝试使用负值索引needle[j]，这导致了错误。
英文:
I don't recall the details of KMP, but just stepping through your code the problem appears to stem from this section:
while (i < n && j < m) {
if (haystack[i] == needle[j]) {
i++;
j++;
if (j == m) {
cout << "occurence at: " << i - j << endl;
j = lps[j - 1];
}
}
else {
if (j > 0) j = lps[j - 1];
else i++;
}
On the iteration of this while loop when i = 9 the line j = lps[j - 1] executes. Since j = 5 on this loop iteration, j is getting set to what lps holds at index 5, namely, -1. On the next iteration of the while loop the code attempts to index needle[j] with a negative value which causes the error.
答案2
得分: 0
Here is the translated content:
"不要使用for循环，改用while循环，当len = lps[len-1]时不要增加i，因为在这一步我们没有为lps[i]分配任何值。
while(i<m) {
if(needle[i]==needle[len]) {
len++;
lps[i]=len;
i++;
}
else {
if(len>0) {
len=lps[len-1]; // 在这里修改了len，但没有给lps[i]赋值
} else {
lps[i]=0;
i++;
}
}
}
```"
<details>
<summary>英文:</summary>
Instead of using a for loop, use a while loop and don't increment i when len = lps[len-1] since we are not assigning any value to lps[i] at this step
while(i<m) {
if(needle[i]==needle[len]) {
len++;
lps[i]=len;
i++;
}
else {
if(len>0) {
len=lps[len-1]; // len is modified here but no value is assigned to lps[i] here
} else {
lps[i]=0;
i++;
}
}
}
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论