Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2672205) | Cod sursa (job #1004588)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
vector < int > sol;
char a[2000007], b[2000007];
int n, m, x;
int p[2000007];
void fa_x (char b[], int i)
{
while(x > 0 && a[x + 1] != b[i])
x = p[x];
if(a[x + 1] == b[i])
++ x;
}
void make_prefix()
{
for(int i = 2; i <= m; ++ i)
{
fa_x(a, i);
p[i] = x;
}
}
int main()
{
int nr2 = 0 ;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a + 1);
gets(b + 1);
m = strlen(a + 1);
n = strlen(b + 1);
make_prefix();
x = 0;
int ok = 0;
for(int i = 1; i <= n; ++ i)
{
fa_x(b, i);
if(x == m)
{
x = p[m];
sol.push_back(i - m);
if(sol.size() > 1000)
sol.erase(sol.begin(), sol.begin() + 1);
}
}
int nr = 1000;
printf("%d\n", (int)sol.size()) ;
for(int i = 0; i < min(nr, (int)sol.size()); ++ i)
printf("%d ", sol[i]);
return 0 ;
}