dl720125's blog

By dl720125, history, 9 months ago, In English

Recently,I encountered a Runtime Error problem with C++. I wrote a code like this:

#include <bits/stdc++.h> #define MOD 1000000007ll #define maxn 1000000 using namespace std; int t,num[maxn+10]; char c[maxn+10]; vector<int> v[maxn+10],res; struct KMP { int n; vector<int> f; KMP(const char *s) : n(strlen(s)), f(n) { int p = -1; f[0] = -1; for (int i = 1; i < n; i++) { while (p != -1 && s[p + 1] != s[i]) p = f[p]; if (s[p + 1] == s[i]) p++; f[i] = p; } } int &operator[](int x) { return f[x]; } } ; inline void dfs(int x,int pr,int w) { res.push_back(x); while(w+1<res.size()&&res[w+1]<=x/2) w++; num[x]=w; for(int i=0;i<v[x].size();i++) if(v[x][i]!=pr){ dfs(v[x][i],x,w); } res.pop_back(); } int main() { cin>>t; for(int h=1;h<=t;h++) { memset(num,0,sizeof(num)); scanf("%s",c); KMP f(c); int len=strlen(c); for(int i=len;i>=1;i--) f[i]=f[i-1]; for(int i=1;i<=len;i++) f[i]++; for(int i=1;i<=len;i++) v[i].clear(); for(int i=1;i<=len;i++){ v[i].push_back(f[i]); v[f[i]].push_back(i); } int root=0; dfs(root,-1,-1); long long ans=1ll; for(int i=1;i<=len;i++){ ans=ans*(long long)(num[i]+1ll); ans%=MOD; } if(h<t) cout<<ans<<endl; else cout<<ans; } return 0; }

When I ran this program with

1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxpuvf

The program showed Runtime Error.

And when I debug it, it showed: SIGTRAP trace/breakpoint trap.

So what is the problem?

Can anyone work it out?

Thanks in advance.

  • Vote: I like it
  • +10
  • Vote: I do not like it

9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

main.cpp:14: KMP(const char *s) : n(strlen(s)), f(n + 1)

9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Since in this case the problem is vector bound overflow, you can just run the code in bound-checking mode and it'll return the error. To get the stack trace you have to run the program in GDB too.