Блог пользователя sourabh912

Автор sourabh912, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.