2018年3月美团春招笔试题 字符串距离

题目：

字符串距离

时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符的数量。如串”aab”与串”aba”的距离为 2；串”ba”与串”aa”的距离为 1；串”baa”和串”baa”的距离为 0。下面给出两个字符串 S 与 T，其中 S 的长度不小于 T 的长度。我们用|S|代表 S 的长度，|T|代表 T 的长度，那么在 S 中一共有|S|-|T|+1 个与 T 长度相同的子串，现在你需要计算 T 串与这些|S|-|T|+1 个子串的距离的和。

输入

第一行包含一个字符串 S。

第二行包含一个字符串 T。

S 和 T 均由字符 a 和 b 组成，1 ≤ |T| ≤ |S| ≤10⁵ 。

输出

输出对应的答案。

样例输入

aab

aba

样例输出

2

Hint

Input Sample 2

aaabb

bab

Output Sample 2

5

在样例 2 中，”aaa”与”bab”的距离为 2，”aab”与”bab”的距离为 1，”abb”与”bab”的距离为 2，

所以最后答案为 5。

这个题目的数据量是|T|<|S|<10^5

所以直接暴力的解法是O（|S|*|T|）肯定会超时的。

我的解法是O（|S|）的，肯定不会超时了。

关键词：反演

具体思路：对于T中的每个字符，都是要和S中的连续|S|-|T|+1个字符相比较的。

比如T中的第1个字符，要和S的前|S|-|T|+1个字符相比较

T中的第2个字符，要和S的第2个字符到第|S|-|T|+2个字符相比较

。。。。。。

每次统计T中的1个字符和S中的|S|-|T|+1个字符有多少个是不一样的，

当统计T中的下一个字符时，S中的|S|-|T|+1个字符只要往右移一步就行，就是去掉第一个字符，再在最后一个字符后面补一个新的字符。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      char s[100001], t[100001];
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	cin >> s >> t;
     
    
   

    

     

    
    

     
	int a = 0, b = 0, ls = strlen(s), lt = strlen(t), su = 0;
     
    
   

    

     

    
    

     
	for (int i = 0; i < ls - lt + 1; i++)if (s[i] == 'a')a++; else b++;
     
    
   

    

     

    
    

     
	for (int i = ls - lt; i < ls; )
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (t[i - ls + lt] == 'a')su += b; else su += a;
     
    
   

    

     

    
    

     
		if (s[i - ls + lt] == 'a')a--; else b--;
     
    
   

    

     

    
    

     
		if (s[++i] == 'a')a++; else b++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	cout << su;
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/79660588