Pagini recente » Cod sursa (job #1069688) | Cod sursa (job #1130870) | Cod sursa (job #2098084) | Cod sursa (job #3239544) | Cod sursa (job #2883113)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6 + 6;
int pi[NMAX];
void buildPi(string &a)
{
int i, j;
pi[0] = 0;
for(i = 1; i < a.length(); ++i)
{
j = pi[i-1];
while(j != 0 && a[j] != a[i])
j = pi[j-1];
if(a[j] == a[i])
++j;
pi[i] = j;
}
pi[a.length()] = 0;
a += "#";
}
int main()
{
string a, b;
vector <int> sol;
fin >> a >> b;
buildPi(a);
int i, j;
j = 0;
for(i = 0; i < b.length(); ++i)
{
if(b[i] == a[j])
{
++j;
}
else
{
while(j !=0 && a[j] != b[i])
j = pi[j-1];
if(a[j] == b[i])
++j;
}
if(j >= a.length() - 1)
sol.push_back(i - (a.length() - 1) + 1);
}
fout << sol.size() << '\n';
j = 0;
for(auto &it: sol)
{
++j;
fout << it << ' ';
if(j == 1000)
break ;
}
return 0;
}