KMP string algo.txt

// KMP try to find lenght of longest proper prefix which is also suffix
void solve(){
        ll i,j,k,l,n,m,x,y,z,r;
        
        string s,t;
        cin>>t>>s; // t is pattern s is string
        m=t.sz;
        s=t+'#'+s;
        // cout<<s<<endl;
        n=s.sz;
        vector<int> f(n+11);
        f[0]=0;
        for(i=1;i<n;i++){
                
                j= f[i-1];
                while(j>0 && s[i]!=s[j]){
                        j=f[j-1];
                }
                if(s[i]==s[j])j++;
                f[i]=j;
        }

        ll ans=0;
        for(i=0;i<n;i++){
                if(f[i]==m)ans++;
        }
        cout<<ans<<endl;
        
        
}