Pagini recente » Cod sursa (job #711964) | Cod sursa (job #1752499) | Cod sursa (job #2964877) | Cod sursa (job #336299) | Cod sursa (job #2781690)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s)
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
#define modulo 1000000007
#define FOR(i,a,b) for(int i=a;i<=b;i++)
typedef vector<pii> vpii;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>res;
void KMP(string a, string b)
{
int n = b.length();
int lps[n];
lps[0] = 0;
int i=0, j=1;
while(j<n)
{
if(b[i] == b[j])
{
lps[j] = i+1;
i++;j++;
}
else if(i==0)
{
lps[j] = 0;
j++;
}
else i = lps[i-1];
}
int m = a.length();
j=0,i=0;
while(j<m || (j>=m && (j-i)<m))
{
if(b[i] == a[j%m])
{
j++;
i++;
if(i == n)
{
res.push_back(j-b.size());
}
}
else if(i==0)
j++;
else i = lps[i-1];
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string a,b;
fin>>a>>b;
KMP(b,a);
fout<<res.size()<<'\n';
for(auto x: res)
fout<<x<<" ";
fin.close();
fout.close();
return 0;
}