これは私が念頭に置いていることですが、O(n^2) です:
例: 入力は「Thisisawesome」です。現在の文字を追加すると、古い対象セットが長くなり意味のあるものになるかどうかを確認する必要があります。しかし、どこまでバックアップする必要があるかを確認するには、先頭までたどる必要があります。例：「awe」と「some」は適切な言葉ですが、「awesome」はより大きな言葉になります。複雑さを改善する方法を提案してください。コードは次のとおりです。
void update(string in)
{
int len= in.length();
int DS[len];
string word;
for(int i=0; i<len; i++) DS[i]=0;
for(int i=0; i<len; i++)
for(int j=i+1; j<=len; j++)
{
word = in.substr(i,j-i);
if(dict.find(word)!=dict.end())
DS[j-1] = (DS[j-1] > word.length()) ? DS[j-1] : word.length();
}
}