Pagini recente » Cod sursa (job #1284123) | Cod sursa (job #1793334) | Cod sursa (job #1718703) | Cod sursa (job #2669752) | Cod sursa (job #2203345)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
ifstream f (in);
ofstream g (out);
int const NM = 2000007;
char pat [NM] , v [NM];
int lps [NM];
int n , m ;
vector <int> v2;
/// lps
void LPS()
{
int l = 0 , i = 1;
while(i < n)
{
if(pat [i] == pat [l])
{
++ l;
lps [i] = l;
++ i;
}
else
{
if(l )
l = lps [l - 1];
else
lps [i] = 0 , ++ i;
}
}
}
int ans;
void kmp ()
{
int i , j;
i = j = 0;
while(i < m)
{
if(pat [j] == v [i])
++ i , ++ j;
if(j == n)
{
++ ans , v2 . push_back (i - j) ;
j = lps [j - 1];
}
else
if(i < m && pat [j] != v [i])
{
if(j)
j = lps [j - 1];
else
++ i;
}
}
}
int main()
{
int i , j , l ;
f >> pat >> v ;
n = strlen(pat);
m = strlen(v);
LPS();
kmp ();
g << ans << '\n';
for(i = 0 ; i < min(ans , 999) ; ++ i)
g << v2 [i] << ' ';
return 0;
}