#include<iostream>
#include<string.h>
using namespace std;
int next[1000];
int KMP(string s1,string s2) {
int i=0,j=0;
while(i<(int)s1.length()&&j<(int)s2.length()) {
if(j==-1||s1.substr(i,1)==s2.substr(j,1)) {
++i;
++j;
}
else j=next[j];
}
if(j>=(int)s2.length())
return i-s2.length();
else return -1;
}
void getnext(string s) {
int j=0,k=-1;
next[0]=-1;
while(j<(int)s.length()) {
if(k==-1||s.substr(j,1)==s.substr(k,1)) {
++j;
++k;
next[j]=k;
}
else k=next[k];
}
}
int main() {
int t,i,j;
cin>>t;
string s[1000][10];
for(i=0;i<t;i++)
for(j=0;j<2;j++)
cin>>s[i][j];
for(i=0;i<t;i++) {
for(j=s[i][1].length()-1;j>=0;j--)
s[i][1].append(s[i][1].substr(j,1));
}
for(i=0;i<t;i++)
getnext(s[i][1]);
for(i=0;i<t;i++)
if(KMP(s[i][0],s[i][1])==0)
cout<<-1<<endl;
else cout<<KMP(s[i][0],s[i][1])<<endl;
return 0;
}
uj5u.com熱心網友回復：
題目照片不清，看不清要求不過，getnext(s[i][1]); 如果s[i][1]的長度大于1000（s[i][1]之前被append，長度真說不準），next[j]=k;的next陣列就有可能越界
uj5u.com熱心網友回復：
問題描述：回文串是指正序、逆序都一樣的字串，如aba,abba。s-1是指s的逆序。
給定一個數T，表示接下來有T組資料。
每組資料包括S和P（長度都小于1000），中間用空格隔開。請在S中找出第一個形如PP-1的回文子串并輸出起始下標，若沒找到輸出-1。
uj5u.com熱心網友回復：
題目說是小于1000，我把陣列已經設定成1000了，但還是越界，請問怎么改呢？
uj5u.com熱心網友回復：
cin>>s[i][j]; //假設這里輸入了長度1000for(i=0;i<t;i++) {
for(j=s[i][1].length()-1;j>=0;j--)
s[i][1].append(s[i][1].substr(j,1)); //這里append就會超過1000
所以getnext(s[i][1]); 的next陣列就有可能越界
uj5u.com熱心網友回復：
假設最大是1000，加上逆序一共2000，我把next陣列大小擴增到3000還是不行
uj5u.com熱心網友回復：
運行結果對同時越界這個不矛盾, int a[100]; a[100] = 10; cout << a[100]; 很大概率會列印出10，你能說這個結果對代碼就對嗎uj5u.com熱心網友回復：
但是我把next陣列設成10000也不對，根據題目字串長度小于1000，一個字符對應一個next值，就算加上逆序后的next值個數也不可能超過10000，不清楚哪里越界了
uj5u.com熱心網友回復：
你這個代碼能編譯通過？uj5u.com熱心網友回復：
沒看明白你的getnext函式是什么目的而且你的 KMP 也不對
給你寫個sample，你自己參考吧
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
char S[1001], P[1001];
int *result = new int[T];
int i, j, k=0, t, ls, lp;
for (i=0; i<T; i++, k++) {
scanf("%s %s", S, P);
ls = (int)strlen(S); //S的長度
lp = (int)strlen(P); //P的長度
result[k] = -1;
if (ls < 2*lp) { //如果S的長度小于P長度的2倍則下一組（S要包含P和P-1，長度必須大于等于P的長度的2倍）
continue;
}
for (j=0; j<=ls-2*lp; j++) {//從S的 j 位置開始回圈查找
if (memcmp(S+j, P, lp)==0) { //如果S+j開始包含P
for (t=0; t<lp && S[j+lp+t]==P[lp-t-1]; t++); //查找S+j+lp位置開始是否包含P-1（如果中途就退出回圈，則t不會到達lp）
if (t==lp) { //t到達lp則說明S+j+lp包含P-1
result[k] = j; //則保存找到的 j 位置
break;
}
}
}
}
for (i=0; i<T; i++) {
printf("%d\n", result[i]);
}
delete []result;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/107189.html
標籤：C++ 語言
上一篇：clion環境配置出錯，cmake出錯，導致簡單main.cpp程式不能執行
下一篇：求教m結果怎么算的