Pagini recente » Cod sursa (job #2535390) | Cod sursa (job #1488716) | Cod sursa (job #1943105) | Cod sursa (job #235878) | Cod sursa (job #2366312)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6;
int g[NMAX];
string a , b;
void precalc()
{
int st;
g[0] = -1;
st = -1;
for(int i = 1; i < a.size(); i++)
{
while(st > -1 and a[i] == a[st + 1])st = g[st];
if(a[i] == a[st + 1])st++;
g[i] = st;
}
}
int idx , i;
vector < int > ans;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
precalc();
idx = 0;
for(i = 0; i < b.size(); i++)
{
while(b[i + idx] == a[idx])idx++;
if(idx == a.size())ans.push_back(i);
idx = g[idx] + 1;
}
fout << ans.size() << "\n";
for(i = 0; i < ans.size(); i++)
fout << ans[i] << " ";
return 0;
}