Pagini recente » Cod sursa (job #1775149) | Cod sursa (job #1920353) | Cod sursa (job #857956) | Cod sursa (job #518085) | Cod sursa (job #1675938)
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
#include <string.h>
#define nMax 2000001
#define pb push_back
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, nrSol;
int pi[nMax], Sol[1001];
char A[nMax], B[nMax];
void read()
{
fin>>A+1>>B+1;
n=strlen(A+1);
m=strlen(B+1);
}
void kmp(char A[], char B[])
{
int k=0;
for(int i=2;i<=n;i++)
{
while(k && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
k=0;
for(int i=1;i<=m;i++)
{
while(k && A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==n)
{
nrSol++;
if(nrSol<=1000)
Sol[nrSol]=i-n;
k=pi[k];
}
}
}
void solve()
{
kmp(A, B);
}
void write()
{
fout<<nrSol<<'\n';
for(int i=1;i<=min(nrSol, 1000);i++)
fout<<Sol[i]<<" ";
}
int main()
{
read();
solve();
write();
return 0;
}