Tìm chuỗi con ngắn nhất của chuỗi thứ nhất sao cho chuỗi con đó không chứa trong chuỗi thứ hai

[Tuong_Le (Tường Lê)]

Xin chào mọi người, em đang học về cây tiền tố, nhưng lại bài này em chưa làm được hết. Đề bài như thế này:

Đây là ví dụ:

Ý tưởng giải bài toán là: build prefix tree Text1#Text2 như trong gợi ý của bài toán. Để ý rằng, trong cây tiền tố, những node lá có ký tự # là những node có đường dẫn từ Text1(Type L leaf), ngược lại những node lá có chứa ký tự $ là những node có đường dẫn từ Text2(Type R leaf).
Bước tiếp theo là kiểm tra mọi node lá. 1 trong những đáp án thỏa mãn bài toán là những node thuộc loại L, và kết quả: đường dẫn từ root + ký tự đầu tiên của node lá loại L (ngoại trừ những node lá loại L bắt đầu bằng #). Bởi vì chúng ta không chắc rằng đường dẫn đấy có được share với bất cứ node lá type R nào hay không. Và chỉ cần chọn thêm 1 ký tự đầu tiên của node lá loại L.
Đó là lý thuyết, còn trong thực hành thì có 1 trường hợp nó không thỏa mãn cách giải trên. Ví dụ:

link: http://brenden.github.io/ukkonen-animation/
Như trong hình, có 1 node thỏa mãn điều tất cả điều kiện là node A->A->A#TTT$
thì kết quả sẽ là: AAA, nhưng thực tế, kết quả ví dụ này phải là: A. Em không giải thích được tạo sao hết. Anh chị nào biết chỉ giúp em với, em xin cảm ơn nhiều.
Đây là code, em chú thích 1 tí, Mõi node có 4 thành phần: nextNode: chứa các node tiếp theo, edges: chứa cặp số start Index và length of substring, cặp số result: chứa substring đi từ root và chiều dại của substring đó, preFirst chứa index của đoạn trước nó(làm điều kiện để loại trường hợp node leaf bắt đầu bằng #):
Suffix tree có dạng thế này:

// Week1Problem5.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <iostream>
#include <string>
#include <vector>
#include <limits>
using namespace std;
const int infinite = numeric_limits<int>::max();
struct Node {
	vector<Node*> nextNode;
	vector<pair<int, int>> edges;
	pair<int, int> result = make_pair(0, 0);
	int preFirst = 0;
};
int findLengthSubStr(string text, int startPos1, int startPos2, int length2)
{
	int result = 0;
	while (text[startPos1 + result] == text[startPos2 + result])
	{
		result++;
		if (result == length2 || startPos2 + result == text.size())
			break;
	}
	return result;
}
// build prefix tree
void update_tree(Node* &root, string text, int subStrIndex)
{
	if (subStrIndex >= text.size()) { return; }
	for (int i = 0; i < root->nextNode.size(); i++)
	{
		int startPos = root->edges[i].first;
		int lengthSubStr = findLengthSubStr(text, startPos, subStrIndex, root->edges[i].second);
		if (lengthSubStr > 0 && lengthSubStr < root->edges[i].second)
		{
			Node* oldNode = root->nextNode[i];
			Node* newNode = new Node;
			pair<int, int> partOldNode(startPos + lengthSubStr, root->edges[i].second - lengthSubStr);
			pair<int, int> partNewNode(subStrIndex + lengthSubStr, text.size() - subStrIndex - lengthSubStr);
			Node * middleNode = new Node;
			middleNode->nextNode.push_back(oldNode);
			middleNode->nextNode.push_back(newNode);
			middleNode->edges.push_back(partOldNode);
			middleNode->edges.push_back(partNewNode);
			root->nextNode[i] = middleNode;
			root->edges[i].second = lengthSubStr;
			return;
		}
		else if (lengthSubStr == root->edges[i].second)
		{
			Node * nextNode = root->nextNode[i];
			update_tree(nextNode, text, subStrIndex + lengthSubStr);
			return;
		}
		else if (lengthSubStr == 0 && i == root->nextNode.size() - 1)
		{
			Node* newNode = new Node;
			std::pair<int, int> newEdge(subStrIndex, text.size() - subStrIndex);
			root->nextNode.push_back(newNode);
			root->edges.push_back(newEdge);
			return;
		}
	}
	Node *nextNode = new Node;
	root->nextNode.push_back(nextNode);
	std::pair<int, int> temp(subStrIndex, text.length() - subStrIndex);
	root->edges.push_back(temp);
	return;
}
void getSubStr(Node* &root, string text, int firstSign, pair<int, int> &result)
{
	//DFS
	for (int i = 0; i < root->nextNode.size(); i++)
	{
		if (root->result.first == 0 && root->result.second == 0)
		{
			root->nextNode[i]->result.first = root->edges[i].first;
			root->nextNode[i]->result.second = root->edges[i].second;
		}
		else
		{
			root->nextNode[i]->result.first = root->edges[i].first - root->result.second;
			root->nextNode[i]->result.second = root->edges[i].second + root->result.second;
		}
		root->nextNode[i]->preFirst = root->edges[i].first;
		getSubStr(root->nextNode[i], text, firstSign, result);
		if (i == root->nextNode.size() - 1) { return; }
	}
	if (root->result.first >= firstSign) { return; }
	if (root->preFirst == firstSign) return;

	if (result.first == infinite || root->preFirst - root->result.first < result.second - result.first)
	{
		result.first = root->result.first;
		result.second = root->preFirst;
		return;
	}
}
string solve(string p, string q)
{
	string result;
	vector<string> notcommon;
	Node* root = new Node;
	string newString = p + '#' + q + '$';
	for (int i = 0; i < newString.length(); i++)
	{
		string subStr = newString.substr(i, newString.length() - i);
		update_tree(root, newString, i);
	}
	pair<int, int> temp(infinite, infinite);
	getSubStr(root, newString, p.size(), temp);
	result = newString.substr(temp.first, temp.second - temp.first + 1);
	return result;
}

int main(void)
{
	string p;
	cin >> p;
	string q;
	cin >> q;
	string ans = solve(p, q);
	cout << ans << endl;
	return 0;
}

[Tuong_Le (Tường Lê)]

Em muốn hỏi thêm là em hay lăn tăn mấy cái pointer này lắm. Ví dụ như em muốn lưu Node vào 1 stack thì lưu Node* vào, rồi lưu vào biến tạm temp, nhưng khi pop ra khỏi stack thì temp nó cũng mất luôn, vì stack nó chỉ lưu cái địa chỉ. Làm sao để lưu cả 1 node vào luôn ạ?

stack<Node*> st;
st.push(root);
Node * temp = st.top();
st.pop();