Before posting this question, I checked the existing questions related to Segmentation fault and yet I am unable to resolve my error.
I am trying to run a c program for the following input but I am facing segmentation fault error.
Input:
4
gitohro qf ejvh i
3
gor
pih
sto
Expected output:
gitohro i
I get the expected output when I hardcode the input in my program. But when I take the input from user/console, I get Segmentation fault error.
Actual error message:
/bin/sh: line 1: 22094 Segmentation fault: 11 gtimeout 4s ./main < input.txt > output.txt [Finished in 1.3s with exit code 139] [cmd: ['g -11 main.cpp -o main && gtimeout 4s ./main<input.txt>output.txt']]
I checked all the indexes to see if it is array out of bound issue but I am not sure what I am doing wrong. Please guide.
My complete code:
#include <bits/stdc .h>
using namespace std;
struct node{ //TrieNode
char c;
int ends;
string word;
node *child[26];
};
struct node *getNode(char c) //get newnode
{
node *newnode = new node;
newnode->c = c;
newnode->ends = 0;
newnode->word = "";
for(int i=0;i<26; i)
newnode->child[i] = NULL;
return newnode;
}
node *root = getNode('/'); //root
//Trie INSERT
void insert(string s)
{
node *curr=root;
int index,i=0;
while(s[i])
{
index = s[i]-'a';
if(curr->child[index]==NULL)
curr->child[index] = getNode(s[i]);
curr=curr->child[index];
i =1;
}
curr->ends = 1;
curr->word = s;
}
void solve(vector<vector<char>>& board,int i,int j,int r,int c,vector<string>& ans,node *curr)
{
//Base case
//If the trie doesn't have the current char OR cell is Visited
int index = board[i][j]-'a';
if(board[i][j]=='$' || curr->child[index]==NULL)
return;
curr = curr->child[index];
if(curr->ends > 0)
{
ans.push_back(curr->word);
curr->ends -=1;
}
//Body
char ch = board[i][j]; //Store current char
board[i][j] = '$'; //Mark current node visited
if(i>0) //TOP
solve(board,i-1,j,r,c,ans,curr);
if(i<r-1) //DOWN
solve(board,i 1,j,r,c,ans,curr);
if(j>0) //LEFT
solve(board,i,j-1,r,c,ans,curr);
if(j<c-1) //RIGHT
solve(board,i,j 1,r,c,ans,curr);
if(i>0 && j>0) //TOP LEFT
solve(board,i-1,j-1,r,c,ans,curr);
if(i<r-1 && j>0) //DOWN LEFT
solve(board,i 1,j-1,r,c,ans,curr);
if(i<r-1 && j<c-1) //DOWN RIGHT
solve(board,i 1,j 1,r,c,ans,curr);
if(i>0 && j<c-1) //TOP RIGHT
solve(board,i-1,j 1,r,c,ans,curr);
board[i][j] = ch; //Mark current node as Unvisited by restoring the value
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
int r=board.size();
int c=board[0].size();
//Insert all words in TRIE
for(int i=0;i<words.size(); i)
insert(words[i]);
//Now search words
vector<string> ans;
for(int i=0;i<r; i)
{
for(int j=0;j<c; j)
solve(board,i,j,r,c,ans,root);
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
vector<string> w ;
vector<vector<char>> x;
int o,p;
cin>>o;
for (int i = 0; i < o; i)
{
cin>>w[i];
}
cin>>p;
for (int i = 0; i < p; i)
{
for (int j = 0; j < p; j)
{
cin>>x[i][j];
}
}
/*
vector<string> w = {"gitohro", "qf", "ejvh", "i"};
vector<vector<char>> x = {
{'g','o','r'},
{'p','i','h'},
{'s','t','o'}
};
*/
vector<string> res = findWords(x,w);
for(auto i:res)
cout<<i<<" ";
return 0;
}
/*
Input 1:
4
gitohro qf ejvh i
3
gor
pih
sto
Output 1:
gitohro i
*/
CodePudding user response：
Your main() is reading user input into empty vectors. You are not adding any entries to them, so your use of vector::operator[] is causing undefined behavior (if you were to replace vector::operator[] with vector::at(), you would get std::out_of_range exceptions thrown).
When you hard-code the input, you are populating the vectors with actual entries correctly.
To fix this, try the following instead:
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
vector<string> w;
vector<vector<char>> x;
int o, p;
cin >> o;
w.resize(o); // <-- ADD THIS!
for (int i = 0; i < o; i)
{
cin >> w[i];
}
cin >> p;
x.resize(p, vector<char>(p)); // <-- ADD THIS!
for (int i = 0; i < p; i)
{
for (int j = 0; j < p; j)
{
cin >> x[i][j];
}
}
vector<string> res = findWords(x, w);
for(auto i : res)
cout << i << " ";
return 0;
}
Alternatively:
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int o, p;
cin >> o;
vector<string> w(o); // <-- INIT HERE!
for (int i = 0; i < o; i)
{
cin >> w[i];
}
cin >> p;
vector<vector<char>> x(p, vector<char>(p)); // <-- INIT HERE!
for (int i = 0; i < p; i)
{
for (int j = 0; j < p; j)
{
cin >> x[i][j];
}
}
vector<string> res = findWords(x, w);
for(auto i : res)
cout << i << " ";
return 0;
}
Alternatively, use vector::push_back() instead of vector::operator[]:
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
vector<string> w;
vector<vector<char>> x
int o, p;
cin >> o;
w.reserve(o);
for (int i = 0; i < o; i)
{
string s;
cin >> s;
w.push_back(s);
}
cin >> p;
x.reserve(p);
for (int i = 0; i < p; i)
{
vector<char> v;
v.reserve(p);
for (int j = 0; j < p; j)
{
char ch;
cin >> ch;
v.push_back(ch);
}
x.push_back(v):
}
vector<string> res = findWords(x, w);
for(auto i : res)
cout << i << " ";
return 0;
}