Pagini recente » Cod sursa (job #2612465) | Cod sursa (job #1588107) | Cod sursa (job #2042358) | Cod sursa (job #700930) | Cod sursa (job #2718060)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
int ct = 0;
int pattern[2000000];
vector <int> v;
void Pattern(string s1)
{
int i = 0;
int j = 1;
pattern[0] = 0;
while(j < s1.size())
{
if(s1[i] == s1[j])
{
i++;
pattern[j] = i;
j++;
}
else
{
if(i != 0)
i = pattern[i - 1];
else
{
pattern[j] = 0;
j++;
}
}
}
}
void KMP(string s1, string s2)
{
int i = 0;
int j = 0;
while(i < s2.size())
{
if(s2[i] == s1[j])
{
i++;
j++;
}
if(j == s1.size())
{
ct++;
if(v.size() < 1000)
v.push_back(i - s1.size());
j = pattern[j - 1];
}
if(s2[i] != s1[j])
{
if(j != 0)
j = pattern[j - 1];
i++;
}
}
}
int main()
{
fin >> s1 >> s2;
Pattern(s1);
KMP(s1, s2);
fout << ct << '\n';
for(int i = 0; i < v.size(); i++)
fout << v[i] <<' ';
return 0;
}