Sony GO FOR IT 3)暗号検索の高速化

i)

# coding: utf-8
# ライセンス：このプログラムは、好きに使ってください。

import sys

# 問題のランダム文字列を生成
def makerandom():
    R = []
    r = 16
    for i in xrange(3000000):
        r = (r*1103515245+12345)&0xFFFFFFFF
        R += [chr(0x61+(26*(r/0x10000))/0x10000)]
    open("random.txt","w").write("".join(R))

#makerandom()
#exit()

key = sys.argv[1]
keyr = key[::-1]
R = raw_input()
for s in xrange(1,len(R)):
    for i in xrange(len(R)):
        t = R[i:i+len(key)*s:s]
        if t==key or t==keyr:
            print "%s,%s"%(s,i+1) 

ii)

//  ライセンス：このプログラムは、好きに使ってください。

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <ctime>
#include <cstdio>
using namespace std;

int main( int argc, char **argv )
{
    //  ランダム文字列
    string R;
    getline(cin,R);
    int N = (int)R.length();
    //  キーワード
    string key = argv[1];
    int n = (int)key.length();
    
    //  キーワードが回文かどうか
    string keyr = key;
    reverse(keyr.begin(),keyr.end());
    bool pal = key==keyr;
    
    //  キーワードの2文字目の出現位置
    vector<int> S;
    for ( int i=0; i<N; i++ )
        if ( R[i]==key[1] )
            S.push_back(i);
    
    //  キーワードが出現するスキップ数と位置
    vector<pair<int,int> > K;
    
    for ( int i=0; i<N; i++ )
    if ( R[i]==key[0] )
    {
        //  進行状況を表示
        if ( i%100==0 )
            printf( "%d/%d (%d%%) found %d\r", i, N, i*100/N, (int)K.size() );
        
        for ( int j=0; j<(int)S.size(); j++ )
        {
            //  スキップ数
            int s = S[j]-i;
            
            //  回文の場合は負の方向は考えない
            if ( pal && s<0 )
                continue;
            
            //  3文字目以降をチェック
            bool f = true;
            for ( int k=2, a=i+s*2; k<n&&f; k++, a+=s )
                if ( a<0 || N<=a || key[k]!=R[a] )
                    f = false;
            
            //  キーワードが出現している
            if ( f )
                if ( s>=0 )
                    K.push_back( make_pair(s,i+1) );
                else
                    K.push_back( make_pair(-s,i+s*(n-1)+1) );
        }
    }
    
    //  ソートして出力
    sort( K.begin(), K.end() );
    
    printf( "\n" );
    for ( int i=0; i<(int)K.size(); i++ )
        printf( "%d,%d\n", K[i].first, K[i].second );
    
    printf( "%.2f sec.\n", (float)clock()/CLOCKS_PER_SEC );
    
    return 0;
}