Pagini recente » Cod sursa (job #1368178) | Cod sursa (job #609349) | Cod sursa (job #1766478) | Cod sursa (job #560208) | Cod sursa (job #3329013)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define NMAX 2000000
char A[NMAX+5],B[NMAX+5];
int n,m,cnt,lps[NMAX+5];
queue <int> q;
void buildPrefix()
{
int i, k=0;
n=strlen(A);
for (i=2; i<=n; i++)
{
while (k && A[k] != A[i-1]) k = lps[k];
if (A[k] == A[i-1]) k++;
lps[i]=k;
}
}
void potrivire()
{
int i, k = 0;;
m=strlen(B);
for (int i = 0; i < m; i++)
{
while (k && A[k] != B[i]) k = lps[k];
if (A[k] == B[i]) k++;
if (k==n)
{
cnt++;
if (cnt<1000) q.push(i-n+1);
}
// poziția pe care începe subșirul A de lungime n în B, știind că se termină pe poziția i
}
}
int main()
{
fin.getline (A,NMAX);
fin.getline (B,NMAX);
buildPrefix();
potrivire();
fout<<cnt<<'\n';
while (!q.empty())
{
fout<<q.front()<<" ";
q.pop();
}
return 0;
}