Marlon’s StringTime Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
SubmitStatus
Description
Long long ago, there was a coder named Marlon. One day he picked two string on the street.A problem suddenly crash his brain…
Let Si..j denote the i-th character to the j-th character of string S.
Given two strings S and T. Return the amount of tetrad (a,b,c,d) which satisfySa..b + Sc..d = T , ab andcd.
The operator + means concate the two strings into one.
Input
The first line of the data is an integer Tc.Following Tc test cases, each contains two line. The first line isS. The second line is T.The length of S and T are both in range [1,100000]. There are only letters in string S and T.
Output
For each test cases, output a line for the result.
Sample Input
1
aaabbb
ab
Sample Output
9

KMP
wordtexttextiword
wordtextworditext
i0strlen(word)

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdio>
 
using namespace std;
 
long long sum1[100010], sum2[100010];
long long ans;
int p[100010];
char s[100010], t[100010];
 
void getNext(char str[], int next[]){
    int i, j = -1;
    int len = strlen(str);
    next[0] = -1;
    for(i = 1; i < len; i ++){
        next[i] = -1;
        while(j > -1 && str[i] != str[j+1])
            j = next[j];
        if(str[i] == str[j+1]){
            j ++;
            next[i] = j;
        }
    }
}
 
void getMatch1(char str[], int next[], char text[]){
    int tlen = strlen(text), slen = strlen(str);
    int i, j = -1;
    for(i = 0; i < tlen; i ++){
        while(j != -1 && text[i] != str[j+1])
            j = next[j];
        if(text[i] == str[j+1]){
            j ++;
            sum1[j]++;
            //printf("fj=%df", j);
        }
    }
    for(i = slen-1; i > 0; i --){
        if(next[i] > -1)
            sum1[next[i]] += sum1[i];
    }
}
 
void getMatch2(char str[], int next[], char text[]){
    int tlen = strlen(text), slen = strlen(str);
    int i, j = -1;
    for(i = 0; i < tlen; i ++){
        while(j > -1 && text[i] != str[j+1])
            j = next[j];
        if(text[i] == str[j+1]){
            j ++;
            sum2[j]++;
            //printf("fj=%df", j);
        }
    }
    for(i = slen-1; i > 0; i --){
        if(next[i] > -1)
            sum2[next[i]] += sum2[i];
    }
}
 
int main(){
    int n;
    int i;
    scanf("%d", &n);
    while(n --){
        memset(sum1, 0, sizeof(sum1));
        memset(sum2, 0, sizeof(sum2));
        scanf("%s %s", s, t);
        int sl = strlen(s);
        int tl = strlen(t);
        long long ans = 0;
        getNext(t, p);
        getMatch1(t, p, s);
        //for(i = 0; i < tl ; i ++)
            //printf("%d\n", sum1[i]);
        //printf("a");
        for(i = 0; i + i < sl; i ++)
            swap(s[i], s[sl - 1 - i]);
        for(i = 0; i + i < tl; i ++)
            swap(t[i], t[tl - 1 - i]);
        getNext(t, p);
        getMatch2(t, p, s);
        ans = 0;
        for(i = 0; i < tl - 1 ; i ++){
            ans += sum1[i] * sum2[tl - 2 - i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}