英文:
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 stepwhile(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>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论