CFR 349 C. Reberland Linguistics ( DP )

http://codeforces.com/contest/667/problem/C
Misunderstood the problem, thought some valid suffix must be some substring of the prefix and failed...
Seems like everyone else had no problem understanding that it actually only wanted us to compute all distinct substrings with length 2 or 3, such that the substring before it has length more than 4, and the substring after it can be decomposed into substrings with length 2 or 3 as well, where no such decomposed substrings are identical.
Simply, this could be solved recursively, taking either length 2 or 3 substring from the suffix, with DP record table to cut off unnecessary recomputing.

string s;

set< string > ans;
set< pair< int, string > > vis;

void dfs( int n, const string &pre ){
    if( n <= 6 ) return;
    if( vis.count( pair< int, string >( n, pre ) ) ) return;
    vis.insert( pair< int, string >( n, pre ) );
    if( s.substr( n - 2, 2 ) != pre ){
        ans.insert( s.substr( n - 2, 2 ) );
        dfs( n - 2, s.substr( n - 2, 2 ) );
    }
    if( n <= 7 ) return;
    if( s.substr( n - 3, 3 ) != pre ){
        ans.insert( s.substr( n - 3, 3 ) );
        dfs( n - 3, s.substr( n - 3, 3 ) );
    }
}

void solve(){
    cin >> s;
    dfs( s.size(), "#$%" );
    cout << ( int ) ans.size() << "\n";
    for( set< string >::iterator it = ans.begin(); it != ans.end(); ++it )
        cout << *it << "\n";
}