sourabh912's blog

By sourabh912, 10 years ago, In English

I am trying to solve Autocomplete Problem and implementing trie solution for it. I am getting segmentation fault when the length of the input string is 10^6. It seems to be a out of memory issue and I am not able to figure out where I am going wrong. The link to the solution is here . Please help !!

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Segmentation fault may be due to the recursive solution (Stack Overflow at that 10^6 recursion depth.) I did use an iterative version and got AC.

#include <bits/stdc++.h>
using namespace std;
const int N = 1234567;
struct trie
{
	char data;
	struct trie *child[26];
	trie(){
		for(int i = 0; i<26; i++) child[i] = NULL;
		data = ' ';
	}
};
trie *T, *head;
int res = 0;
trie *newNode(char s){
	trie *nn = (trie *)malloc(sizeof(trie));
	nn->data = s;
	return nn;
}
void insert(char *s)
{
	int len = strlen(s);
	int ptr = 0, pref_cnt = 0;;
	head = T;
	bool ok = false;
	while (ptr < len){
		if (head->child[s[ptr]-'a'] != NULL){
			head = head->child[s[ptr]-'a'];
			ptr++;
		}
		else{
			if (!ok){
				res += ptr+1;
				ok = true;
			}
			head->child[s[ptr]-'a'] = newNode(s[ptr]);
		}
	}
	if (!ok) res+=len;
}
void dfs(trie *t)
{
	if (t == NULL) return ;
	cout << t->data <<" ";
	for(int i = 0; i<26; i++)
		dfs(t->child[i]);
}
void solve(int test)
{
	int n;res = 0;
	T = newNode('$');
	scanf("%d", &n);
	char s[N];
	for(int i = 0; i<n; i++){
		scanf("%s", s);
		insert(s);
	}
	//dfs(T);
	printf("Case #%d: %d\n", test, res);
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 1; i<=t; i++)
		solve(i);
	return 0;
}
			

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's most probably because of the stack size limit, had a very similar code and happened to me too, as suggested by pikaynu, you can implement it iteratively or you can increase the stack size limit and it will work on your PC but may or may not work on the judge's depending on the stack size there.