Pagini recente » Cod sursa (job #1084894) | Cod sursa (job #605396) | Cod sursa (job #1398885) | Cod sursa (job #1106254) | Cod sursa (job #2404124)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Dim = 2 * 1e6 + 5;
char A[Dim],B[Dim],C[Dim];
int Z[Dim];
vector < int > V;
int main() {
fin >> (A + 1) >> (B + 1);
int n = strlen(A + 1), m = strlen(B + 1);
int idk = 0;
for ( int i = 1; i <= n; ++i)
C[++idk] = A[i];
C[++idk] = '$';
int ss = idk;
for ( int i = 1; i <= m; ++i)
C[++idk] = B[i];
n = idk;
Z[1] = n;
int l = 0, r = 0;
for (int i = 2 ; i <= n; ++i) {
if ( r >= i) Z[i] = min(r-i+1,Z[i-l+1]);
while ( C[i+Z[i]] == C[Z[i]+1]) Z[i]++;
if ( r < i + Z[i] - 1) r = i+Z[i]-1, l = i;
}
for ( int i = ss + 1; i <= n; ++i)
if( Z[i] >= ss - 1)
V.push_back(i -ss);
fout << V.size() << "\n";
for ( const auto i : V)
fout << i-1 << " ";
}