Description

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，

分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。

Input

两行两个字符串，分别代表S和T

Output

第一行一个正整数k，表示T在S中出现了几次

接下来k行正整数，分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出，S下标从0开始。

Sample Input

bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab

a?aba?abba

Sample Output

0

HINT

S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母， T中只包含小写字母和“?”

Solution

将字符串转化

对于每个位置，如果 \(s_i\) 为正常字母，那么赋值为 \(s_i-96\) ，如果是问号，那么赋值为 \(0\)

S赋值出的数组是 \(x\) ，T赋值出的数组是 \(y\)

令S中一个位置的权值为 \(f(i)=\sum_{j=0}^{i}(x_{i-j}-y_{len_T-j})^2y_{i-j}\)

那么如果在S中以 \(i\) 位置结尾的子串能够和T匹配，\(f(i)=0\)

这还是不好算，但是这形式就是在提示我们要用套路了

把 \(y\) 数组反过来， \(f(i)=\sum_{j=0}^{i}(x_{i-j}-y_{j})^2y_{j}\)

拆开， \(f(i)=\sum_{j=0}^ix_{i-j}^2y_j-2x_{i-j}y_j^2+y_j^3\)

两个卷积加上一个三次方权值和

FFT求解就好了

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst db Pi=acos(-1.0);const int MAXN=1<<19;int n1,n2,n,m,rev[MAXN],sum,f[MAXN],cnt,nt,ans[MAXN];char s1[MAXN],s2[MAXN];struct Complex{    db real,imag;    inline Complex operator + (const Complex &A) const {        return (Complex){real+A.real,imag+A.imag};    };    inline Complex operator - (const Complex &A) const {        return (Complex){real-A.real,imag-A.imag};    };    inline Complex operator * (const Complex &A) const {        return (Complex){real*A.real-imag*A.imag,imag*A.real+real*A.imag};    };};Complex x[MAXN],y[MAXN],xf[MAXN],yf[MAXN];template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline void FFT(Complex *A,int tp){ for(register int i=0;i
             
              >1);++j) { Complex A1=A[i+j],A2=w*A[i+j+(l>>1)]; A[i+j]=A1+A2;A[i+j+(l>>1)]=A1-A2; w=w*wn; } } }}int main(){ scanf("%s",s1);scanf("%s",s2); n1=strlen(s1);n2=strlen(s2); m=n1+n2-1; for(n=1;n
              
               <<=1)cnt++; for(register int i=0;i
               
                >1]>>1)|((i&1)<<(cnt-1)); for(register int i=0;i