某島

… : "…アッカリ~ン . .. . " .. .
April 5, 2012

SGU 506. Subsequences Of Substrings

Brief description:

斬頭去尾而不傷及加密內容的方案數。

Analysis:

… . 掃一遍吧。

string T, P;
int n, m; LL res;

int main(){

    //freopen("in.txt", "r", stdin);
    
    cin >> T >> P, n = SZ(T), m = SZ(P);
    int _i = -1;
    for (int i=0;i<n;++i){
        if (T[i] == P[0]){
            int i_ = i + 1, j = 1;
            while (i_ < n && j < m){
                if (T[i_] == P[j]) ++j;
                ++i_;
            }
            if (j < m) break;

            res += LL (i - _i) * (n - i_ + 1);            
            _i = i;
        }
    }

    cout << res << endl;
}

External link:

http://acm.sgu.ru/problem.php?contest=0&problem=506