Pagini recente » Cod sursa (job #1794037) | Cod sursa (job #424537) | Cod sursa (job #1804375) | Cod sursa (job #1435868) | Cod sursa (job #1107434)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 2000015
char A[NMAX],B[NMAX];
int P[NMAX];
int N, M;
int Antwort;
vector < int > Sol;
void Scannen()
{
freopen("strmatch.in","r",stdin);
fgets(A+1,NMAX - 3,stdin);
fgets(B+1,NMAX - 3,stdin);
N = strlen(A+1)-1;
M = strlen(B+1)-1;
}
void Losen()
{
int q = 0;
for(int i=2;i<=N;i++)
{
while(q && A[q+1] != A[i])
q = P[q];
if(A[q+1] == A[i])
q++;
P[i] = q;
}
q = 0;
for(int i=1;i<=M;i++)
{
while(q && A[q+1] != B[i])
q = P[q];
if(A[q+1] == B[i])
q++;
if(q == N)
{
q = P[N];
++Antwort;
if(Antwort <= 1000)
Sol.push_back(i-N);
}
}
}
void Drucken()
{
freopen("strmatch.out","w",stdout);
printf("%d\n",Antwort);
for(vector < int > ::iterator it = Sol.begin(); it != Sol.end(); ++ it)
printf("%d ",*it);
}
int main()
{
Scannen();
Losen();
Drucken();
return 0;
}