// Boyer-Moore.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <stdio.h>
#include <stdlib.h>
#include <fstream>

#define BUFFER_SIZE 2000000

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

char s[BUFFER_SIZE],p[BUFFER_SIZE];

unsigned int strlen(const char* s)
{
    if (s == nullptr)
        return 0;
    unsigned int i = 0;
    while (s[i] != '\0')
        ++i;
    return i;
}
void printArray(int* a, const  int& len, bool show_0s = true)
{
    for (int i = 0;i < len;++i)
        if (show_0s == true || a[i] != -1)
            printf("%2i ", a[i]);
    printf("\n");
}

void buildLps(const char* s, int* lps)
{
    int n = strlen(s);
    lps[n - 1] = n - 1;
    int i = n - 1, j = n - 2;
    while (j >= 0)
    {
        if (s[i] == s[j])
        {
            --i;
            lps[j] = i;
            --j;
        }
        else
        {
            if (i == n - 1)
            {
                lps[j] = n - 1;
                --j;
            }
            else
                i = lps[i + 1];
        }
    }
}

void buildGoodSuffixArray(const char* s, int* gs)
{
    int lps[BUFFER_SIZE];
    buildLps(s, lps);   
    int n = strlen(s);
    for (int i = 0;i < n;++i)
        gs[i] = 0;
    gs[n] = 1;
    for (int i = 0;i < n;++i)
    {
        int pos = lps[i];
        if (s[pos + 1] == s[i])
            gs[pos + 1] = pos + 1 - i;
    }
    int j = lps[0]+1;
    for (int i = 0;i < n;++i)
    {
        if (gs[i] == 0)
            gs[i] = j;
        if (i == j)
            j = lps[j] + 1;
    }
    gs[n] = 1;

}

void buildLastApArray(const char* s,int *ap)
{
    int i;
    for (i=0;i < 256;++i)
        ap[i] = -1;
    i = 0;
    while (s[i] != '\0')
    {
        ap[s[i]]=i;
        ++i;
    }
}

void boyer_moore(const char* s, const char* p)
{
    int nr=0;
    int ap[1000];
    int last_ap[256];
    buildLastApArray(p,last_ap);
    int gs[BUFFER_SIZE];
    buildGoodSuffixArray(p, gs);
    int n = strlen(s);
    int m = strlen(p);
    int i = 0, j;
    while (i <= n - m)
    {
        j = m - 1;
        while (j >= 0)
        {
            if (s[i + j] != p[j])
                break;
            --j;
        }
        if (j < 0)
        {
            ap[nr++] = i;
            ++i;
            continue;
        }
        int pos1 = i, pos2 = i;
        int last = last_ap[(unsigned int)s[i+j]];
        if (last == -1)
            pos1 += j + 1;
        else if (last > j)
            ++pos1;
        else
            pos1 += j - last;
        pos2 += gs[j+1];
        i = (pos1 > pos2) ? pos1 : pos2;

    }

    fout << nr << '\n';
    for (i = 0;i < nr;++i)
        fout << ap[i] << ' ';
}

int main()
{
    fin >> s >> p;
    boyer_moore(s, p);
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file