C ++ string :: find complex

Perché lo string::find() implementato da c ++ non usa l’ algoritmo KMP (e non funziona in O(N + M) ) e gira in O(N * M) ? È corretto in C ++ 0x? Se la complessità della ricerca corrente non è O(N * M) , che cos’è?

PS: Scusa intendo string::find()

quindi quale algoritmo è implementato in gcc? è quel KMP? se no, perché? L’ho provato e il tempo di esecuzione indica che viene eseguito in O(N * M)