Pagini recente » Cod sursa (job #1611988) | Cod sursa (job #1678245) | Cod sursa (job #1364055) | Cod sursa (job #504202) | Cod sursa (job #2207119)
#include <cstdio>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;
int const NM = 2e6 + 7;
char pat [NM] , v [NM];
int lps [NM] , n , m , best;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
vector <int> sol;
inline void Lps ()
{
int i , j ;
int a = 0 , b = 1;
while(b < m)
{
if(pat [a] == pat [b])
{
++ a;
++ b;
lps [b - 1] = a;
}
else
{
if(a)
a = lps [a - 1];
else
lps [b] = 0 , ++ b;
}
}
return;
}
int main()
{
FILE *cin , *cout;
int i , j;
cin = fopen (in , "r");
cout = fopen (out , "w");
fgets (pat , NM , cin);
fgets (v , NM , cin);
n = strlen (v) - 1;
m = strlen (pat) - 1;
Lps ();
for(i = 0 , j = 0 ; j < n ; )
{
if(pat [i] == v [j])
{
++ i;
++ j;
}
if(i == m)
{
++ best;
sol . push_back (j - i);
i = lps [m - 1];
}
else
if(j < n && pat [i] != v [j] )
if(i)
i = lps [i - 1];
else
++ j;
}
fprintf (cout , "%d\n" , best);
best = min (best , 1000);
for(i = 0 ; i < best ; ++ i)
fprintf (cout , "%d " , sol [i]);
return 0;
}