天梯赛-找密码

#include
#include
using namespace std;
char str[1000005];
int  dp1[30][2], dp2[1000005];
int main() {
    int N;
    cin >> N;
    for (int n = 0; n < N; n++) {
        int i, len = 0;
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        dp2[0] = 1;
        cin >> str;
        for (i = 0; str[i]; i++) {
            len = 0x3f3f3f3f;
            for (int j = 0; j < 26; j++) {
                if (len > dp1[j][0] + 1) len = dp1[j][0] + 1, dp2[i + 1] = dp2[dp1[j][1]];
                else if (len == dp1[j][0] + 1) dp2[i + 1] = (dp2[i + 1] + dp2[dp1[j][1]]) % 1000000007;
            }
            dp1[str[i] - 'a'][0] = len;
            dp1[str[i] - 'a'][1] = i+1;
        }
        len = 0x3f3f3f3f;
        for (int j = 0; j < 26; j++) {
            if (len > dp1[j][0] + 1) len = dp1[j][0] + 1, dp2[i + 1] = dp2[dp1[j][1]];
            else if (len == dp1[j][0] + 1) dp2[i + 1] = (dp2[i + 1] + dp2[dp1[j][1]]) % 1000000007;
        }
        cout << "Case #" << n + 1 << ':' << endl
            << len << ' ' << dp2[i + 1] << endl;
    }
    return 0;
}