Suffix Trie Construction

Input

string = "babc"

Output

{
    "c": {"*": true},
    "b": {
    	"c": {"*": true},
        "a": {"b": {"c": {"*": true}}},
    },
    "a": {"b": {"c": {"*": true}}},
}

---

Solution #1

// time: O(N^2)
// space: O(N^2)
class SuffixTrie {
    constructor(){
       this.root={};
    }
     
    populateSuffixTrieFrom(string){
     for(let i=0; i<string.length;i++){
       let trie=this.root; 
       for(let j=i; j<string.length;j++){
         const curChar=string[j]; //
         if(!trie[curChar]) trie[curChar]={};
         trie=trie[curChar];//
       }
       trie["*"]=true; 
     }
   }
  }
  let string="babc";
  const suffixTrie = new SuffixTrie();
  
  suffixTrie.populateSuffixTrieFrom(string);
  console.log(JSON.stringify(suffixTrie.root));

Time Complexity

O(N^2)

N: string의 길이
2개의 for문을 돌면서 string의 suffix에 해당하는 문자를 trie에 넣기 때문

Space Complexity

O(N^2)

N: string의 길이
가장 길이가 긴 suffix는 string 자기 자신이기 때문에, 가장 크게 만들어질수 있는 trie의 크기는 NxN이 될것이다.

---

Solution #2

// b a b c
// time: O(N)
// N: string.length, M: longest trie length =N
// space: O(N^2)

/*
curRef=[{}]
    babc
    s
    { 
        b:{  
            c:{ <----

            }
            a:{ 
                b:{
                    c:{ <----
                    }
                }
            }
        }
        c:{}
        a:{}
    }
*/
const populateSuffixTrieFrom = (string) => {
	const trie = {};
	const store = {};
	let curRef = [trie];

  	for (let s = 0; s < string.length; s++) {
		const c = string[s];
		const tmp = [];

		for (let i = 0; i < curRef.length; i++) {
			if (s === string.length - 1) curRef[i][c] = { "*": true };
			else curRef[i][c] = {};
			curRef[i] = curRef[i][c];

			if (!trie[c]) trie[c] = curRef[i];
			// console.log(curRef);

			if (store[c]) tmp.push(store[c]);
			else store[c] = curRef[i];
		}
		curRef.push(tmp);
	}
	return trie;
};

---

Time Complexity

O(N)

N: string의 길이
curRef만큼 for문을 돌며 string의 suffix에 해당하는 문자를 trie에 넣기 때문

Space Complexity

O(N^2)

N: string의 길이
// N: string.length, M: longest trie length =N
가장 길이가 긴 suffix는 string 자기 자신이기 때문에, 가장 크게 만들어질수 있는 trie의 크기는 NxN이 될것이다.