Pagini recente » Cod sursa (job #803333) | Cod sursa (job #1289595) | Cod sursa (job #2720793) | Cod sursa (job #33456) | Cod sursa (job #3030375)
#include <fstream>
const int NMAX=2000005;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX], t[NMAX], a[NMAX];
int n, m, pi[NMAX], d[NMAX];
int ans[NMAX];
void pii(char []);
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
int i, k=0, lg=0;
fin>>a;
for(i=0; a[i]; i++) s[i+1]=a[i];
n=i;
fin>>a;
for(i=0; a[i]; i++) t[i+1]=a[i];
m=i;
pii(s);
for(i=1; i<=m; i++)
{
while(k>0 && t[i]!=s[k+1]) k=pi[k];
if(t[i]==s[k+1]) k++;
d[i]=k;
if(k==n) ans[++lg]=i-n;
}
fout<<lg<<'\n';
for(i=1; i<=min(1000, lg); i++) fout<<ans[i]<<' ';
return 0;
}
void pii(char s[])
{
int k=0, i;
pi[1]=0;
for(i=2; i<=n; i++)
{
while(k>0 && s[i]!=s[k+1]) k=pi[k];
if(s[i]==s[k+1]) k++;
pi[i]=k;
}
}