Pagini recente » Cod sursa (job #177861) | Cod sursa (job #1643913) | Cod sursa (job #1458567) | Cod sursa (job #196211) | Cod sursa (job #2457989)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int NMAX = 2000005;
int phi[2*NMAX];
vector<int>sol;
string s , s1;
void KermitManancaPrune(string s)
{
phi[0] = -1;
for(int i = 1 ; i < s.size() ; i++)
{
int x = i-1;
while(s[phi[x]+1] != s[i] && phi[x]!=-1)
x = phi[x];
if(s[phi[x]+1] == s[i])
phi[i] = phi[x]+1;
else
phi[i] = -1;
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> s1 >> s;
s = (s1+"*"+s);
KermitManancaPrune(s);
for(int i = s1.size()+1 ; i < s.size() ; i++)
{
if(phi[i] == s1.size()-1)
{
sol.push_back(i-s1.size()-s1.size());
}
}
cout << sol.size() << "\n";
int t = sol.size();
int jfc = min(1000,t);
for(int i = 0 ; i < jfc ; i++)
cout << sol[i] << " ";
return 0;
}