Pagini recente » Cod sursa (job #865896) | Cod sursa (job #2972809) | Cod sursa (job #132094) | Cod sursa (job #1222874) | Cod sursa (job #2700931)
#include <bits/stdc++.h>
#define NMAX 2000002
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[NMAX], B[NMAX];
int lps[NMAX],cnt;
vector<int>rasp;
int main()
{
in.getline(A,NMAX);
in.getline(B,NMAX);
int n=strlen(A), m=strlen(B);
if(n>m)
{
out<<'0';
return 0;
}
lps[0]=0;
int l=0;
for(int i=1;i<n;i++)
{
if(A[l]==A[i])
lps[i]=++l;
else
{
if(l==0)
lps[i]=0;
else
{
l=lps[l-1];
i--;
}
}
}
int i=0,j=0;
while(i<m)
{
if(A[j]==B[i])
{
i++;
j++;
}
else
{
if(j==n)
{
cnt++;
if(cnt<=1000)
rasp.push_back(i-n);
}
if(j==0)
i++;
else
j=lps[j-1];
}
}
out<<cnt<<'\n';
for(int i=0;i<1000 && i<cnt;i++)
out<<rasp[i]<<' ';
return 0;
}