AOJ 0528: Common Sub-String

共通部分文字列の長さの最大値を求める問題。
1文字後ろを調べ、同じ文字列を重複して調べないようにすると、TLEしないで解けます。
O(n^3)かO(n^2)です。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string s,t;

int main(){
	while(cin>>s>>t){
		int ans = 0;
		for(int i = 0,ls = s.size(); i < ls; i++){
			for(int j = 0,lt = t.size(); j < lt; j++){
				if(i>0&&j>0&&s[i-1]==t[j-1])continue;
				int r = 0;
				for(int k = 0;i+k<ls&&j+k<lt;k++){
					if(s[i+k]!=t[j+k]){
						break;
					}
					r++;
				}
				ans = max(ans,r);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}