学步园

又是一道优化时间复杂度的算法。

朴素O（N * N） （ N <= 2000000)
可以优化成O（N）的时间复杂度

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;

char word[2001000], str[2000100];
int num[2001000];

int main( )
{
 int N;
 scanf("%d",&N);
 while( N-- )
 {
    scanf("%s%s",str,word);
    int len1 = strlen(word);
    int len2 = strlen(str);
    long long sum = 0;
    for( int i = 0; i < len1; i++)
    {
       if( i < len2 )
           num[str[i]-'a']++;
       sum += (long long) num[word[i]-'a'];
       if( len2 + i - len1 >= 0 )
           num[str[len2+i-len1] -'a']--;
         
    }
    printf("%I64d\n",sum);           
 }
        
}