Оптимизировать задачу на графы

[Poma][a]

#include <string>
#include <iostream>

using namespace std;

struct node {                   // объявление структуры для дерева
	node *children[25];
};

void delete_tree(node *current)
{
	if (current == NULL) return;
	for (int i = 0; i < 25; ++i)
		delete_tree(current->children[i]);
	delete current;
}


int main() {
	node *tree = new struct node;  // выделение памяти для дерева
	for (int i = 0; i < 25; ++i)             // обнуления веток
		tree->children[i] = NULL;

	node *current = tree;// присвоение текущей вершини - первой

	int N, cnt = 1;
	cin >> N; // считываем количество слов
	for (int i = 0; i < N; ++i) {
		string word;
		cin >> word; // считывание слова
		current = tree;
		for (int j = 0; j < word.length(); ++j) { // цикл по количеству символов в слове
			if (current->children[word[j] - 65] == NULL) {         //если элемент  под номером (код символа - 65) = NULL тогда
				current->children[word[j] - 65] = new struct node;// создаем новую ветку, выделяем память.
				current = current->children[word[j] - 65];  //переносим указатель текущей ветки на только, что "созданной ветке"
				cnt++;// увеличиваем счетчик вершин
				for (int m = 0; m < 25; ++m) {  //обнуления подветок только что созданной ветки
					current->children[m] = NULL;
				}
			}
			else {        //если элемент под номером (код символа - 65)  не NULL тогда
				current = current->children[word[j] - 65];// переходим к следующей подветке
			}
		}
	}
	delete_tree(tree);
	cout << cnt << endl;// вывод результата
	return 0;
}

Надо так

[Poma][a]

type
	TPChild = ^TChild;
	TChild = array ['A'..'Z'] of TPChild;

procedure Delete_Tree(root : TPChild);
var
	ch : Char;
begin
	if root = nil then Exit;
	for ch := 'A' to 'Z' do
		Delete_Tree(root^[ch]);
	FreeMem(root)
end;

var
	tree, current : ^TChild;
	n, i, j, cnt : Integer;
	s : string;
        ch : Char;

begin
	GetMem(tree, SizeOf(TChild));

	ReadLn(n);
        cnt := 1;

        for ch := 'A' to 'Z' do
               tree^[ch] := nil;

	for i := 1 to n do begin
		ReadLn(s);
		current := tree;
		for j := 1 to Length(s) do begin
			if current^[s[j]] = nil then begin
				GetMem(current^[s[j]], SizeOf(TChild));
				Inc(cnt);
                                current := current^[s[j]];
                                for ch := 'A' to 'Z' do
                                      current^[ch] := nil;

			end
                        else
                                current := current^[s[j]]
		end
	end;

	Delete_Tree(tree);

	WriteLn(cnt)
end.

Ради прикола переписал на паскаль, посмотрел - память я везде прибираю, но снова памяти мало..
Косяк не в удалении.. оно кажись пральное

[Аватар]

И зачем там array ['A'..'Z']? Из-за этого и память жрет. Вот переделал, прокатило

program Project1;

type
  TPChild = ^TChild;
  TChild = record
    Simbol: Char;
    Children: array of TPChild;
  end;

procedure Delete_Tree(root : TPChild);
var ch : Integer;
begin
  for ch:=0 to High(root^.Children) do Delete_Tree(root^.Children[ch]);
  FreeMem(root)
end;

var
  tree, current : TPChild;
  n, i, j, k, m : Integer;
  cnt: longint;
  s : string;

begin

  GetMem(tree, SizeOf(TChild));
  ReadLn(n);
  cnt := 1;
  for i := 1 to n do begin
    ReadLn(s);
    current := tree;
    for j := 1 to Length(s) do begin
      m:=High(current^.Children)+1;
      for k:=0 to High(current^.Children) do
        if current^.Children[k]^.Simbol=s[j] then begin m:=-k-1; Break; end
        else if current^.Children[k]^.Simbol>s[j] then begin m:=k; Break; end;
      if m>=0 then begin
        SetLength(current^.Children,High(current^.Children)+2);
        if m<High(current^.Children)then Move(current^.Children[m],current^.Children[m+1],SizeOf(TPChild)*(High(current^.Children)-m));
        GetMem(current^.Children[m],SizeOf(TChild));
        current:=current^.Children[m];
        current^.Simbol:=s[j];
        Inc(cnt);
      end
      else current:=current^.Children[-m-1];
    end;
  end;
  Delete_Tree(tree);
  WriteLn(cnt);
end.

[Poma][a]

Супер! Ляпота! Спасибо!

А зачем.. Быстрее было б.. А так, да.. 20*10000*25*2 и еще на что-то умножить малясь перебор..

[Аватар]

Быстрей точно. Только SetLength чего стоит, да и поиск буквы в лоб, можно бинарный, но не думаю что существенно ускорится

[Аватар]

Можно еще так, без массива, быстрей будет точно, а по памяти не знаю

  TChild = record
    Simbol: Char;
    Next: TPChild;
    Children: TPChild;
  end;