SRM 541 Div2 250pt : AkariDaisukiDiv2

問題概要

f(X)=A~X~B~X~Cとなる関数Xがある。A,B,C,Xは空でない文字列である。f(X)=S(|S|<50)となるようなA,B,C,Xの組み合わせが何通りあるか求める問題。

解法

どこで分離するかで全探索する。もちろんXの箇所は長さが同じになるように考えるのだけど、定数小さいからO(N^5)ですむし、if文一個付け加えるだけでO(N^4)に落ちる。

acceptされたコード

#include <string>
using namespace std;

struct AkariDaisukiDiv2 {

	int countTuples(string S) {
		const int L = S.length();

		int ans = 0;
		for(int a=1; a<L; ++a){
			for(int x=a+1; x<L; ++x){
				for(int b=x+1; b<L; ++b){
					for(int xx=b+1; xx<L; ++xx){
						if(S.substr(a, x-a) == S.substr(b, xx-b)){
							++ans;
						}
					}
				}
			}
		}
		return ans;
	}

};