String Matching
タイトル1094:String Matching
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:865
解決:446
タイトルの説明:
Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user. We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters. We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for 1<=j<=m). If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.
入力:
For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.
出力:
You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.
サンプル入力:
サンプル出力:
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:865
解決:446
タイトルの説明:
Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user. We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters. We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for 1<=j<=m). If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.
入力:
For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.
出力:
You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.
サンプル入力:
abababab abab
サンプル出力:
3
#include<iostream>
#include<string>
using namespace std;
int main()
{
int i,j,t;
string s,ss;
while(cin>>s>>ss)
{
j=s.size();
for(i=t=0;i<j;++t)
{
if(s.find(ss,i)!=string::npos) i=s.find(ss,i)+1;
else break;
}
cout<<t<<endl;
}
return 0;
}
/**************************************************************
Problem: 1094
User: 3011216016
Language: C++
Result: Accepted
Time:170 ms
Memory:3052 kb
****************************************************************/