Pagini recente » Cod sursa (job #356668) | Cod sursa (job #256921) | Cod sursa (job #2282491) | Cod sursa (job #542728) | Cod sursa (job #2201773)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005], B[2000005];
int N, M, P[2000005],v[1005];
void prep()
{
int i, k = 0;
for(i = 1; i < M; i++)
{
if(A[i] == A[k]) k++;
else {
k = 0; if(A[i] == A[k]) k++;
}P[i] = k;
}
}
int main()
{
int i, k = 0;
fin.getline(A,2000005); M = strlen(A);
fin.getline(B,2000005); N = strlen(B);
prep();
for(i = 0; i < N; i++)
{
while( k != 0 && (A[k] != B[i]) )
k = P[max(k - 1, 0)];
if( A[k] == B[i] ) k++;
if(k == M)
{
v[min(++v[0],1001)] = i - M + 1;
k = P[M - 1];
}
}
fout << v[0] << "\n";
for(i = 1; i <= min(v[0],1000); i++) fout << v[i] << " ";
return 0;
}