#include <fstream>
#include <cstring>
#include <cmath>
#define NMAX 2000000
#define M101 666013
#define M109 10003

using namespace std;

ifstream a("strmatch.in");
ofstream b("strmatch.out");

struct key { int b101 ; int b109 ;};
struct key sir[NMAX], sub;

char sir1[NMAX],sub1[NMAX];

int main()
{
    a>>sub1>>sir1;
    int m=strlen(sub1);
    int n=strlen(sir1);

    for(int i=0;i<m;i++)
        {
            sub.b101 += sub1[i]*pow(101,m-i-1);
            sub.b109 += sub1[i]*pow(109,m-i-1);
        }
    sub.b101 %= M101;
    sub.b109 %= M109;

    for(int i=0;i<m;i++)
        {
            sir[m-1].b101 += sir1[i]*pow(101,m-i-1);
            sir[m-1].b109 += sir1[i]*pow(109,m-i-1);
        }
    sir[m-1].b101 %= M101;
    sir[m-1].b109 %= M109;

    long long int P101 = pow(101,m-1);
    long long int P109 = pow(109,m-1);

    for(int i=m;i<n;i++)
        {
            sir[i].b101 = (( sir[i-1].b101 - sir1[i-m].b101*P101%M101 + M101 )%M101 + sir1[i] )%M101;
            sir[i].b109 = (( sir[i-1].b109 - sir1[i-m].b109*P109%M109 + M109 )%M109 + sir1[i] )%M109;
        }


            return 0;
}