info about fast distinct-substring computation with suffix arrays/trees

jakobkogler · jakobkogler · commit e949b36d0c07 · 2023-04-22T21:16:29.000+02:00
diff --git a/src/string/string-hashing.md b/src/string/string-hashing.md
@@ -185,6 +185,9 @@ int count_unique_substrings(string const& s) {
 }
 ```
 
+Notice, that $O(n^2)$ is not the best possible time complexity for this problem.
+A solution with $O(n \log n)$ is described in the article about [Suffix Arrays](suffix-array.md), and it's even possible to compute it in $O(n)$ using a [Suffix Tree](./suffix-tree-ukkonen.md) or a [Suffix Automaton](./suffix-automaton.md).
+
 ## Improve no-collision probability
 
 Quite often the above mentioned polynomial hash is good enough, and no collisions will happen during tests.

Original file line number	Diff line number	Diff line change
`@@ -185,6 +185,9 @@ int count_unique_substrings(string const& s) {`
`185`	`185`	`}`
`186`	`186`	```
`187`	`187`
	`188`	`+Notice, that $O(n^2)$ is not the best possible time complexity for this problem.`
	`189`	`+A solution with $O(n \log n)$ is described in the article about [Suffix Arrays](suffix-array.md), and it's even possible to compute it in $O(n)$ using a [Suffix Tree](./suffix-tree-ukkonen.md) or a [Suffix Automaton](./suffix-automaton.md).`
	`190`	`+`
`188`	`191`	`## Improve no-collision probability`
`189`	`192`
`190`	`193`	`Quite often the above mentioned polynomial hash is good enough, and no collisions will happen during tests.`