交替字符串(alternate)

题目描述：

给定一个只包含两种字符的字符串s，如果s的一个子串中不存在两个相邻的字符相同的情况，则认为这是一个交替子字符串。 需要注意的是，两个子串起始位置不同，终止位置不同，则认为他们是不同的子串。 求字符串s的交替子字符串的个数。

输入

从文件 alternate.in 中读入数据。 一行，一个字符串 s，仅包含两种字符。

输出

输出到文件 alternate.out 中一个整数， 表示字符串s的交替子字符串的个数。

输入样例

abbb

输出样例

5

大家通过读题，不一定能看明白，说的是个什么，这时候可以看一下题目给出的样例解释

样例解释

abbb共有“a",”ab","b",”b",”b"五种不同的交替子串 abbb字符串的子串包含有，’a’,’b’,’b’,’b’,’ab’,’bb’,’bb’,’abb’,’bbb’,’abbb’;其中符合题目描述的 “两个子串起始位置不同，终止位置不同，则认为他们是不同的子串”。 “a",”ab","b",”b",”b"

组委会给出的参考 1

#include <bits/stdc++.h>  
using namespace std;  
int cnt;
int main()
{
    //freopen("alternate.in","r",stdin);
    //freopen("alternate.out","w",stdout);
    string s;
    cin>>s;
    int fg=0; 
    for(int i=0;i<s.size();i++)//从尾部开始 
    {
        for(int j=0;j<=i;j++)//从头部开始
        {
            fg=0;
            for(int k=j;k<=i-1;k++) 
            {   
                //判断是否交替，头尾两个位置相等的话，就不是，跳过 
                if(s[k]==s[k+1])
                {
                    fg=1;
                    break;  
                } 
            }
            if(fg==0)
                cnt++;
         } 
    }
    cout<<cnt;
    return 0; 
}

组委会给出的参考 2

#include <bits/stdc++.h>  
using namespace std;  
  
int main()
{
//  freopen("alternate.in","r",stdin);
//  freopen("alternate.out","w",stdout);
    string s;
    cin>>s;
    long long num=1,t=1;
    //遍历字符串 
    for(int i=t;i<s.size();i++)
    {
    	//判断相邻位置是否相同 
        if(s[i-1]==s[i])
        {
        	//相等时，子串自身加 1 ，总数加 1 
            num++;
            t=1;//遍历的起始位置从1开始 代入样例来理解 
        }
        else
        {
            t++;
            num+=t; 
        } 
    } 
    cout<<num;
    return 0;
}

参考 3

#include <bits/stdc++.h>  
using namespace std;  
long long ans=1;
int main()
{
	//freopen("alternate.in","r",stdin);
	//freopen("alternate.out","w",stdout);
	string s;
	cin>>s; 
	for(int i=1,j=0;i<s.size();i++)
	{
		//当前位置和上一位置的字串相同时
		//移动j的位置（头部） 
		if(s[i] == s[i-1])
			j=i;
		ans +=i-j+1;
	}
	cout<<ans;
	return 0; 
 }