Pagini recente » Cod sursa (job #2568918) | Cod sursa (job #3203170) | Cod sursa (job #2053685) | Cod sursa (job #2791294) | Cod sursa (job #2726313)
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[Nmax];
char B[Nmax];
int P[Nmax];
int rez;
void citire()
{
fin>>A;
fin>>B;
}
void prefix()
{
char p[Nmax];
strcpy(p, A);
strcpy(A + 1, p);
strcpy(p, B);
strcpy(B + 1, p);
A[0] = B[0] = ' ';
int i, j = 0;
for(i=2; A[i]; i++)
{
while(j && A[j + 1] != A[i])
{
j = P[j];
}
if(A[j + 1] == A[i])
{
j++;
}
P[i] = j;
}
}
vector<int>poz;
void afisare()
{
fout<<rez<<"\n";
for(int i=0; i<poz.size() ;i++)
{
fout<<poz[i]<<" ";
}
}
void rezolvare()
{
int j = 0;
int N = strlen(A) - 1;
for(int i=1; B[i]; i++)
{
while(j && A[j + 1] != B[i])
{
j = P[j];
}
if(A[j + 1] == B[i])
j++;
if(j == N)
{
rez++;
if (rez <= 1000)
poz.push_back(i - N);
}
}
afisare();
}
int main()
{
citire();
prefix();
rezolvare();
return 0;
}