KMP

from sys import stdin
def input(): return stdin.readline().rstrip()

def getFail(P):
    Plen=len(P)
    ret=[0]*Plen
    j=0
    for i in range(1,Plen):
        while j>0 and P[i]!=P[j]:
            j=ret[j-1]
        if P[i]==P[j]:
            j+=1
            ret[i]=j
    return ret

def KMP(T, P):
    ret=[]
    Tlen=len(T)
    Plen=len(P)
    j=0
    for i in range(Tlen):
        while j>0 and T[i]!=P[j]:
            j=fail[j-1]
        if T[i]==P[j]:
            if j==Plen-1:
                ret.append(str(i-Plen+2))
                j=fail[j]
            else:
                j+=1
    return ret

target=str(input())
ref=str(input())
fail=getFail(ref) # List
res=KMP(target,ref)
print(len(res))
print(" ".join(res))

 

#include <bits/stdc++.h>
using namespace std;

string src, tar;
vector<int> fail, KMP;

vector<int> getFail(string t) {
	vector<int> ret(t.length());
	int j = 0;
	for (int i = 1; i < t.length(); ++i) {
		while (j > 0 && t[i] != t[j]) j = ret[j - 1];
		if (t[i] == t[j]) ret[i] = ++j;
	}

	return ret;
}

vector<int> getKMP(string s, string t) {
	vector<int> ret;
	int sLen = s.length(), tLen = t.length(), j = 0;

	for (int i = 0; i < sLen; ++i) {
		while (j > 0 && s[i] != t[j]) j = fail[j - 1];
		if (s[i] == t[j]) {
			if (j == tLen - 1) {
				ret.push_back(i - tLen + 1 + 1);
				j = fail[j];
			}
			else j++;
		}
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	getline(cin, src); getline(cin, tar);
	fail = getFail(tar);
	KMP = getKMP(src, tar);

	cout << KMP.size() << "\n";
	for (int i : KMP) {
		cout << i << " ";
	}

	return 0;
}

 

BOJ https://www.acmicpc.net/problem/1786