SRM455 Div2 Medium(500) EasySequence

Aの先頭N個と同じ数列が出てくれば以降は同じ数列が生成されるので検索を打ち切る。N≦7なのでAは長くとも10⁷程度にしかならない。

#include <vector>
#include <numeric>

using namespace std;

class EasySequence
{
public:
    int find( vector <int> A, vector <int> B );
    bool cmp( vector<int>::iterator a, vector<int>::iterator b, int n );
};

int EasySequence::find( vector <int> A, vector <int> B )
{
    int N = (int)A.size();
    int M = (int)B.size();

    for ( int i=0; ; i++ )
    {
        while ( (int)A.size() < i + max(N,M) )
            A.push_back( accumulate( A.end()-N, A.end(), 0 ) % 10 );

        if ( cmp( A.begin()+i, B.begin(), M ) )
            return i;

        if ( i > 0  &&  cmp( A.begin()+i, A.begin(), N ) )
            return -1;
    }
}

//  a, bからn文字が等しいか調べる
bool EasySequence::cmp( vector<int>::iterator a, vector<int>::iterator b, int n )
{
    for ( int i=0; i<n; i++, a++, b++ )
        if ( *a != *b )
            return false;
    return true;
}

Pythonが使いたい……。

class EasySequence:
    def find(s,A,B):
        N=len(A)
        M=len(B)
        i=0
        while True:
            while len(A) < i+max(N,M):
                A.append(sum(A[-N:])%10)
            if A[i:i+M] == B:
                return i
            if i > 0 and A[i:i+N] == A[:N]:
                return -1
            i+=1

if __name__ == "__main__":
    e=EasySequence()
    print e.find([1,2,3],[0,7,8,5])
    print e.find([1,2,8],[7,4,2,3])
    print e.find([1,2,3,4,5],[4,5])
    print e.find([1],[1,1,1])
    print e.find([1,2,3,4,5,9,7],[7,3,1,3,9,2,5,0,3,3,5,7,5,8,1,2,1,9,3,9,3,8,5,8,5,1,9,9,5,2,9,0,5,9,9,9,3,4,9,8,1,3,7,5,7,0,1,4,7])