#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> bmpSearch(const std::string &text, const std::string &pattern);

vector<int> computeBmpLast(const std::string &pattern);

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    string needle;
    string haystack;

    f >> needle >> haystack;

    f.close();

    vector<int> solutions = bmpSearch( haystack, needle );

    g << solutions.size() << "\n";
    for( int i = 0; i < solutions.size() && i < 1000; i++ )
        g << solutions[i] << " ";

    g << "\n";

    g.close();

    return 0;
}



vector<int> bmpSearch(const std::string &text, const std::string &pattern)
{
    size_t textSize = text.size();
    size_t patternSize = pattern.size();

    vector<int> solutions;

    vector<int> bmpLast = computeBmpLast(pattern);
    size_t tIdx = patternSize - 1;
    size_t pIdx = patternSize - 1;
    while(tIdx < textSize){
        if(pattern[pIdx] == text[tIdx]){
            if(pIdx == 0){   //found a match
                solutions.push_back( tIdx );
                if( tIdx + pattern.size() > text.size() )
                {
                    tIdx += ( pattern.size() + 1 );
                    pIdx = patternSize ;
                }
            }
            tIdx--;
            pIdx--;
        }
        else {
            //Character Jump Heuristics
            int lastOccur = bmpLast[text[tIdx]];
            tIdx = tIdx + patternSize - min<int>(pIdx, 1 + lastOccur);
            pIdx = patternSize - 1;
        }
    }
    return solutions;
}


vector<int> computeBmpLast(const std::string &pattern)
{
    const size_t NUM_ASCII_CHARS = 128;
    vector<int> bmpLast(NUM_ASCII_CHARS);
    for(size_t i = 0; i < NUM_ASCII_CHARS; i++){
        bmpLast[i] = -1;
    }
    for(size_t i = 0; i < pattern.size(); i++){
        bmpLast[pattern[i]] = i;
    }
    return bmpLast;
}