Pagini recente » Cod sursa (job #3269693) | Cod sursa (job #1453995) | Cod sursa (job #2496388) | Cod sursa (job #1997690) | Cod sursa (job #2299809)
#include <bits/stdc++.h>
#define Nmax 2*2000000+100
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char pat[Nmax], str[Nmax];
int phi[Nmax], m, sol;
vector <int> Sol;
inline void build_phi(char pat[] , int x)
{
int rez=0;
phi[0]=0;
for(int i = 1 ; i <= x ; i++ )
{
while(rez !=0 && pat[i] != pat[rez])
{
rez = phi[rez-1];
}
if(pat[i] == pat[rez])
{
rez++;
}
phi[i] = rez;
}
}
inline void solve()
{
strcat(pat, "#");
strcat(pat, str);
int x = strlen(pat);
build_phi( pat , x );
for(int i = 0 ; i < x ; i ++ )
{
if(phi[i] == m && i>=m)
{
sol++;
Sol.push_back(i);
}
}
g<<sol<<'\n';
for(int i = 0 ; i < Sol.size() ; i++)
{
g<<Sol[i] - 2*m << " ";
}
}
int main()
{
f.getline(pat , 2000000);
f.getline(str , 2000000);
m = strlen(pat);
solve();
return 0;
}