#include <iostream>
#include <vector>
using namespace std;
vector<int> table(const string &w){
	int n = w.size();
	vector<int> t(n+1,-1);
	int c = 0;
	int p = 1;
	while(p<n){
		if(w[p]==w[c])	t[p] = t[c];
		else{
			t[p] = c;
			c = t[c];
			while(c>=0&&w[p]!=w[c])
				c = t[c];
		}
		p++;	c++;
	}
	t[p] = c;
	return t;
}
vector<int> match(const string &s, const string &w){
	vector<int> t = table(w);
	cout<<"Table values of the word:"<<endl;
	for(int i=0; i<w.size(); i++)	cout<<w[i]<<'\t';
	cout<<endl;
	for(int i=0; i<t.size(); i++)	cout<<t[i]<<'\t';
	cout<<endl<<endl;
	int n = s.size();
	int j = 0;
	int k = 0;
	vector<int> p;
	while(j<n){
		if(w[k]==s[j]){
			j++;	k++;
			if(k==w.size()){
				p.push_back(j-k);
				k = t[k];
			}
		}
		else{
			k = t[k];
			if(k<0){
				j++; k++;
			}
		}
	}
	return p;
}
int main() {
	string s;
	string w;
	cin>>s>>w;
	vector<int> ans = match(s,w);
	cout<<"The given word is matched in the string at following positions:"<<endl;
	for(int x: ans)	cout<<x<<' ';
	cout<<endl;
	cout<<s<<endl;
	int j=0;
	for(int i=0; i<s.size()&&j<ans.size(); i++){
		if(i==ans[j]&&++j)	cout<<'^';
		else	cout<<' ';
	}
	cout<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2ZWN0b3I8aW50PiB0YWJsZShjb25zdCBzdHJpbmcgJncpewoJaW50IG4gPSB3LnNpemUoKTsKCXZlY3RvcjxpbnQ+IHQobisxLC0xKTsKCWludCBjID0gMDsKCWludCBwID0gMTsKCXdoaWxlKHA8bil7CgkJaWYod1twXT09d1tjXSkJdFtwXSA9IHRbY107CgkJZWxzZXsKCQkJdFtwXSA9IGM7CgkJCWMgPSB0W2NdOwoJCQl3aGlsZShjPj0wJiZ3W3BdIT13W2NdKQoJCQkJYyA9IHRbY107CgkJfQoJCXArKzsJYysrOwoJfQoJdFtwXSA9IGM7CglyZXR1cm4gdDsKfQp2ZWN0b3I8aW50PiBtYXRjaChjb25zdCBzdHJpbmcgJnMsIGNvbnN0IHN0cmluZyAmdyl7Cgl2ZWN0b3I8aW50PiB0ID0gdGFibGUodyk7Cgljb3V0PDwiVGFibGUgdmFsdWVzIG9mIHRoZSB3b3JkOiI8PGVuZGw7Cglmb3IoaW50IGk9MDsgaTx3LnNpemUoKTsgaSsrKQljb3V0PDx3W2ldPDwnXHQnOwoJY291dDw8ZW5kbDsKCWZvcihpbnQgaT0wOyBpPHQuc2l6ZSgpOyBpKyspCWNvdXQ8PHRbaV08PCdcdCc7Cgljb3V0PDxlbmRsPDxlbmRsOwoJaW50IG4gPSBzLnNpemUoKTsKCWludCBqID0gMDsKCWludCBrID0gMDsKCXZlY3RvcjxpbnQ+IHA7Cgl3aGlsZShqPG4pewoJCWlmKHdba109PXNbal0pewoJCQlqKys7CWsrKzsKCQkJaWYoaz09dy5zaXplKCkpewoJCQkJcC5wdXNoX2JhY2soai1rKTsKCQkJCWsgPSB0W2tdOwoJCQl9CgkJfQoJCWVsc2V7CgkJCWsgPSB0W2tdOwoJCQlpZihrPDApewoJCQkJaisrOyBrKys7CgkJCX0KCQl9Cgl9CglyZXR1cm4gcDsKfQppbnQgbWFpbigpIHsKCXN0cmluZyBzOwoJc3RyaW5nIHc7CgljaW4+PnM+Pnc7Cgl2ZWN0b3I8aW50PiBhbnMgPSBtYXRjaChzLHcpOwoJY291dDw8IlRoZSBnaXZlbiB3b3JkIGlzIG1hdGNoZWQgaW4gdGhlIHN0cmluZyBhdCBmb2xsb3dpbmcgcG9zaXRpb25zOiI8PGVuZGw7Cglmb3IoaW50IHg6IGFucykJY291dDw8eDw8JyAnOwoJY291dDw8ZW5kbDsKCWNvdXQ8PHM8PGVuZGw7CglpbnQgaj0wOwoJZm9yKGludCBpPTA7IGk8cy5zaXplKCkmJmo8YW5zLnNpemUoKTsgaSsrKXsKCQlpZihpPT1hbnNbal0mJisraikJY291dDw8J14nOwoJCWVsc2UJY291dDw8JyAnOwoJfQoJY291dDw8ZW5kbDsKCXJldHVybiAwOwp9

YWJjZGFiY2RhYmNkYWIKYWJjZGFiY2Q=

abcdabcdabcdab
abcdabcd