Pagini recente » Cod sursa (job #663059) | Cod sursa (job #2636305) | Cod sursa (job #2660862) | Cod sursa (job #1718611) | Cod sursa (job #1968523)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define nmax 2000010
char a[nmax],b[nmax];
int n,m,i,ans[1010],nr,pi[nmax];
void prefix()
{
pi[1]=0;
int k=0;
for (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;
}
}
void kmp()
{
int q=0;
for (i=1; i<=m; i++)
{
while (q&&a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
q++;
if (q==n)
{
q=pi[n];
nr++;
if (nr<=1000)
ans[nr]=i-n;
}
}
}
int main()
{
fin >> a >> b;
n=strlen(a);
m=strlen(b);
for (i=n; i; i--)
a[i]=a[i-1];
for (i=m; i; i--)
b[i]=b[i-1];
prefix();
kmp();
fout << nr << '\n';
for (i=1; i<=min(1000,nr); i++)
fout << ans[i] << ' ';
fout << '\n';
// for (i=1; i<=n; i++)
// fout << pi[i] << ' ';
}