Codeforces contest 1056 problem E Check Transcription —— 字元串hash

One of Arkady’s friends works at a huge radio telescope. A few decades ago the telescope has sent a signal s towards a faraway galaxy. Recently they’ve received a response t which they believe to be a response from aliens! The scientists now want to check if the signal t is similar to s.

The original signal s was a sequence of zeros and ones (everyone knows that binary code is the universe-wide language). The returned signal t, however, does not look as easy as s, but the scientists don’t give up! They represented t as a sequence of English letters and say that t is similar to s if you can replace all zeros in s with some string r0 and all ones in s with some other string r1 and obtain t. The strings r0 and r1 must be different and non-empty.

Please help Arkady’s friend and find the number of possible replacements for zeros and ones (the number of pairs of strings r0 and r1) that transform s to t.

Input

The first line contains a string s (2≤|s|≤105) consisting of zeros and ones — the original signal.

The second line contains a string t (1≤|t|≤106) consisting of lowercase English letters only — the received signal.

It is guaranteed, that the string s contains at least one ‘0’ and at least one ‘1’.

Output

Print a single integer — the number of pairs of strings r0 and r1 that transform s to t.

In case there are no such pairs, print 0.

Examples

inputCopy

01

aaaaaa

outputCopy

4

inputCopy

001

kokokokotlin

outputCopy

2

Note

In the first example, the possible pairs (r0,r1) are as follows:

“a”, “aaaaa”

“aa”, “aaaa”

“aaaa”, “aa”

“aaaaa”, “a”

The pair “aaa”, “aaa” is not allowed, since r0 and r1 must be different.

In the second example, the following pairs are possible:

“ko”, “kokotlin”

“koko”, “tlin”

題意：

給你一個01串和一個字元串，讓你0和1映射成不同的字元串使得讓01串變成下面的字元串有多少種方法。

題解：

用string的方法會t，他提示的是hash，那麼我們可以先hash出下面的字元串，然後枚舉一遍0轉換的字元串的長度，由于有1的限制，其實找的情況并不多，然後算0的hash值就是末尾的hash值-開頭的hash值*末尾-開頭的距離，就是這段區間的hash值，是以預處理一下就好了，之後for一遍01串，看看這樣子得到的hash值是否等于原來字元串的hash值。

這也是從别人那裡看來的，現在就知道了hash[pos]-hash[pos-i]就是區間pos-i到i這段的hash值。

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define ll long long 
const ll mod=1e9+7;
const int N=1e5+5,M=1e6+5;
ll has[M],p[M];
ll cal(int sta,int fin)
{
	return (has[fin]-has[sta]*p[fin-sta]%mod+mod)%mod;
}
char s[N],t[M];
int main()
{
	p[0]=1; 
	scanf("%s%s",s,t);
	int sta0,sta1,num0=0,num1=0;
	int lens=strlen(s),lent=strlen(t);
	for(int i=lens-1;~i;i--)
	{
		if(s[i]=='1')
			num1++,sta1=i;
		else 
			num0++,sta0=i;
	}	
	for(int i=1;i<=lent;i++)
		p[i]=p[i-1]*31%mod,has[i]=(has[i-1]*31+t[i-1])%mod;
	int ans=0;
	for(int len0=1;len0*num0+num1<=lent;len0++)
	{
		if((lent-num0*len0)%num1!=0)
			continue;
		int len1=(lent-num0*len0)/num1;
		ll has0=cal(len1*sta0,len1*sta0+len0);//他前面有(sta0-1)*len1長度的1 
		ll has1=cal(len0*sta1,len0*sta1+len1);
		if(has0==has1)
		continue;
		ll sum=0;
		for(int i=0;i<lens;i++)
		{
			sum=(sum*p[s[i]=='0'?len0:len1]+(s[i]=='0'?has0:has1))%mod;//這裡不加括号會執行(...+s[i])==?會導緻錯誤 
		}
		ans+=(sum==has[lent]);
	}
	printf("%d\n",ans);
	return 0;
}