Pagini recente » Monitorul de evaluare | Cod sursa (job #2940783) | Cod sursa (job #3241826) | Cod sursa (job #817450) | Cod sursa (job #2572153)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000010; // TODO: fix
char A[MAX], B[MAX];
int Store[1000], pi[MAX];
int n, m, i, k, nr;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> A >> B;
n = strlen(A);
m = strlen(B);
pi[1] = 0; k = 0;
for(i = 2; i <= n; i ++)
{
while(k > 0 && A[i] != A[k + 1]) k = pi[k];
if(A[i] == A[k + 1]) k ++;
pi[i] = k;
}
k = 0;
for(i = 1; i <= m; i ++)
{
while(A[k + 1] != B[i] && k > 0) k = pi[k];
if(A[k + 1] == B[i]) k ++;
if(k == n)
{
nr ++;
if(Store[0] < 1000)
Store[++Store[0]] = i - n;
}
}
g << nr << "\n";
for(i = 1; i <= Store[0]; i ++)
g << Store[i] << " ";
return 0;
}