Pagini recente » Cod sursa (job #1374526) | Cod sursa (job #2627205) | Cod sursa (job #1088697) | Cod sursa (job #1413787) | Cod sursa (job #932998)
Cod sursa(job #932998)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int Nmax = 2000010;
char S1[Nmax],S2[Nmax],S[Nmax<<1];
int Left,Right,N1,N2,N;
int Z[Nmax<<1];
vector<int> Sol;
int Co;
void Extend(int &left,int &right)
{
int now = right - left + 1;
while ( S[now] == S[right] && right <= N ) ++now , ++right;
}
int main()
{
F.getline(S1,Nmax,'\n'), N1 = strlen( S1 );
F.getline(S2,Nmax,'\n'), N2 = strlen( S2 );
N = N1 + N2;
for (int i=1;i<=N1;++i) S[i] = S1[i-1];
for (int j=N1;j<N;++j) S[j+1] = S2[j-N1];
S[N+1] = '#';
Left = Right = 1 , Z[1] = N;
for (int i=2;i<=N;++i)
{
if ( Left <= i && i <= Right )
{
if ( i+Z[i-Left+1]-1 < Right )
{
Z[i] = Z[i-Left+1];
}
else
{
Left = i;
Extend(Left,Right);
Z[i] = Right - Left, --Right;
}
}
else
{
Left = Right = i;
Extend(Left,Right);
Z[i] = Right - Left, --Right;
}
if ( Z[i] >= N1 && i > N1 )
{
++Co;
if ( Sol.size() < 1000 )
Sol.push_back( i-N1-1 );
}
}
G<<Co<<'\n';
for (vector<int>::iterator it=Sol.begin();it!=Sol.end();++it)
G<<*it<<' ';
G<<'\n';
}