Pagini recente » Cod sursa (job #300486) | Cod sursa (job #3165759) | Cod sursa (job #2977704) | Cod sursa (job #2051365) | Cod sursa (job #2163105)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int nmax = 2000001;
char txt[nmax];
char pat[nmax];
vector <int> lps;
vector <int> sol;
int M,N;
void citire()
{
f>>pat;
M = strlen(pat);
f>>txt;
N = strlen(txt);
}
void setup()
{
int i, len;
i = 1;
len = 0;
lps.push_back(0);
while ( i < M )
{
if( pat[i] == pat [len] )
{
lps.push_back(++len);
++i;
}
else {
if( len != 0 )
len = lps[len-1];
else
{
lps.push_back(0);
++i;
}
}
}
}
void solve ()
{
int i,j;
while( i < N )
{
if ( txt[i] == pat[j] )
{
++i;
++j;
}
if ( j == M)
{
sol.push_back(i-j);
j = lps[j-1];
}
if ( txt[i] != pat[j] && i < N )
{
if ( j != 0)
j = lps[j-1];
else
++i;
}
}
}
int main()
{
citire();
setup();
solve();
int N = sol.size();
g << N << "\n";
if ( N > 1000)
for(int i = 0; i < 1000 ; i++)
g<<sol[i]<< " ";
else
for(int i = 0; i < N ; i++)
g<<sol[i]<< " ";
}