Pagini recente » Cod sursa (job #637864) | Cod sursa (job #784297) | Cod sursa (job #1760991) | Istoria paginii utilizator/mihaipriboi | Cod sursa (job #1689866)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define INF numeric_limits<int>::max()
#define int64 long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<int> sol;
int pi[2000001];
void prefix(string x)
{
int k=0;
for(int i=1;i<(int)x.size();i++)
{
while(x[i]!=x[k] && k>0)
k=pi[k-1];
if(x[i]==x[k])
k++;
pi[i]=k;
}
}
void kmp(string x,string s)
{
prefix(x);
int k=0;
for(int i=0;i<(int)s.size();i++)
{
while(s[i]!=x[k] && k>0)
k=pi[k-1];
if(s[i]==x[k])
k++;
if(k==(int)x.size())
sol.pb(i-x.size()+1);
}
}
int main()
{
in>>a>>b;
kmp(a,b);
out<<sol.size()<<'\n';
for(int i=0;i<min((int)sol.size(),1000);i++)
out<<sol[i]<<' ';
return 0;
}