Count the number of substrings

Question

I would like to ask if there is an algorithm for counting the number of discrete substring events in a string in O (n) time.

Answer 1

[EDIT 11/17/2013: count the leaf nodes. Thanks Vinicius Pinto!]

You can build an entity tree

Answer 2

You can use KMP Algorithm and change it to increase the counter instead of returning.

Another possibility is the Rabin-Karp algorithm , however, it depends on hashing, so you either have to accept the possibility of false positives while maintaining complexity is linear or allows the possibility of quadratic complexity, keeping the results 100% correct.