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; } };