Pagini recente » Cod sursa (job #699009) | Cod sursa (job #2399483) | Cod sursa (job #2112245) | Cod sursa (job #2570524) | Cod sursa (job #2909779)
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[Nmax], s[Nmax];
int pi[Nmax];
int main()
{
fin >> p;
fin >> s;
///prefix function
int n=strlen(p);
for(int i=1;i<n;i++)
{
int k=pi[i-1];
while(k>0 && p[k]!=p[i])
k=pi[k-1];
if(p[k]==p[i])
k++;
pi[i]=k;
}
///matching
int k=0, m=strlen(s);
vector <int> sol;
for(int j=0;j<m;j++)
{
while(k>0 && p[k]!=s[j])
k=pi[k-1];
if(s[j]==p[k])
k++;
if(k==n)
sol.push_back(j-n+1);
}
fout << sol.size() << '\n';
if(sol.size()>1000) sol.resize(1000);
for(auto it:sol)
fout << it << ' ';
return 0;
}